[백준 17218] ⚾

www.acmicpc.net/problem/17281

17281번: ⚾

import itertools,sys

input = sys.stdin.readline
arr = [1,2,3,4,5,6,7,8]

p = itertools.permutations(arr, 8)

N = int(input())
mat = [list(map(int,input().split())) for i in range(N)]

def game(start,t,arr):
    out = 0
    score = 0
    b1,b2,b3 = 0,0,0
    while True:
        if out == 3:
            break

        if t[arr[start]] == 0:
            out+=1
        elif t[arr[start]] == 1:
            score+=b3
            b1,b2,b3 = 1,b1,b2
        elif t[arr[start]] == 2:
            score +=(b2+b3)
            b1,b2,b3 = 0,1,b1
        elif t[arr[start]] == 3:
            score += (b1+b2+b3)
            b1,b2,b3 = 0,0,1
        elif t[arr[start]] == 4:
            score += (1+b1+b2+b3)
            b1,b2,b3 = 0,0,0
        
        start = (start+1)%9
    return start, score

def solve(arr,mat):
    start = 0
    total = 0
    for t in mat:
        start, score = game(start,t,arr) # 몇 번쨰 선수, 선수 정보, 선수 순서
        total += score
    return total

answer = 0
for i in p:
    l = list(i)
    l.insert(3,0)
    answer = max(solve(l,mat),answer)

print(answer)

풀이

먼저 순열을 통해 선수 순서 목록을 모두 생성한다.

4번타자는 1번선수가 치기로 정해져 있으니 나머지 선수들만 정해주면 된다.

8명이니 40320개의 후보가 나온다.

 

40320개의 선수 리스트를 모두 시뮬레이션 돌려 최댓값을 찾으면 된다.

 

방법이 같더라도 최적화가 덜 되면 문제가 틀린다.

base부분을 deque로 만들어 pop, appendleft 로 구현했을 때는 시간초과가 나왔다.

변수의 수를 줄이고, base를 직접 값을 대입하는 방식으로 바꾸니 시간내에 통과했다.

 

하지만 구랻ㅎ python으로는 아무도 통과 못한 문제다. pypy를 사용하자

 

시간복잡도

이닝의 수가 N이라고 하자.

1개의 이닝은 최대 3회 안에 끝난다. (out이 최소 1개 포함되어있기 때문)

선수수가 9명일때 한명씩 게임을 하므로 1이닝에 최대 9*3*N 시간이 걸린다. 즉

시간복잡도는 40320 * O(27N), 상수 생략하면 O(N)이다.