https://www.acmicpc.net/problem/17281

---

1. 코드(시간초과)

from collections import deque

def game(order):
    global ans
    score = 0
    curr = 0
    for l in lst:
        q = deque([0, 0, 0])  # [3루, 2루, 1루]
        out = 0
        while True:
            result = l[order[curr]]
            if result == 0:
                out += 1
            elif result == 1:
                if q.popleft() == 1:
                    score += 1
                q.append(1)
            elif result == 2:
                for _ in range(2):
                    if q.popleft() == 1:
                        score += 1
                q.append(1)
                q.append(0)
            elif result == 3:
                for _ in range(3):
                    if q.popleft() == 1:
                        score += 1
                q.append(1)
                q.append(0)
                q.append(0)
            elif result == 4:
                score += sum(q) + 1
                q = deque([0, 0, 0])


            # 다음 타자(아웃 카운트보다 먼저 위치해야한다)
            curr += 1
            if curr == 9:
                curr = 0
            # 아웃 카운트 증가
            if out == 3:
                break
    ans = max(ans, score)


def dfs(idx, path):
    if idx == 8:
        game(path[0:3] + [0] + path[3:])
        return

    for i in range(len(num)):
        if not v[i]:
            v[i] = True
            dfs(idx+1, path + [num[i]])
            v[i] = False
           
           
ans = 0
num = [1, 2, 3, 4, 5, 6, 7, 8]
v = [False] * 8

N = int(input())
lst = [list(map(int, input().rstrip().split())) for _ in range(N)]
dfs(0, [])
print(ans)

2. 코드(정답)

from collections import deque


def game(order):
    global ans
    score = 0
    curr = 0
    for inning in innings:
        out = 0
        b1 = b2 = b3 = 0
        while True:
            result = inning[order[curr]]

            if result == 0:
                out += 1
            elif result == 1:
                score += b3
                b1, b2, b3 = 1, b1, b2
            elif result == 2:
                score += b2 + b3
                b1, b2, b3 = 0, 1, b1
            elif result == 3:
                score += b2 + b3 + b1
                b1, b2, b3 = 0, 0, 1
            elif result == 4:
                score += 1 + b1 + b2 + b3
                b1 = b2 = b3 = 0

            # 다음 타자(아웃 카운트보다 먼저 위치해야한다)
            curr += 1
            if curr == 9:
                curr = 0
            # 아웃 카운트 증가
            if out == 3:
                break
    ans = max(ans, score)



def dfs(idx, path):
    if idx == 8:
        game(path[0:3] + [0] + path[3:])
        return

    for i in range(len(num)):
        if not v[i]:
            v[i] = True
            dfs(idx+1, path + [num[i]])
            v[i] = False


ans = 0
num = [1, 2, 3, 4, 5, 6, 7, 8]
v = [False] * 8

N = int(input())
innings = [list(map(int, input().rstrip().split())) for _ in range(N)]
dfs(0, [])
print(ans)

---

3. 후기

완전탐색으로 모든 경우를 구하기만 하면 풀릴 줄 알았는데 시간초과가 발생했다.

8! * 50, 대략 이백만번 정도의 경우를 조사하는데 1%에서 시간초과가 발생했다. 충분히 가능한 범위라 생각했는데 고민좀 하다 인터넷에 검색했다.

base를 큐 형태로 풀지 않고 그냥 각각 1루, 2루, 3루 형태의 변수를 사용하는 방식으로 풀게되면 시간초과가 발생하지 않는다.