[BOJ] ⚾ - 17281 (G4)

시간 제한	메모리 제한
2 초	512 MB

문제

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다.

경기는 N이닝 동안 진행된다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 공격과 수비가 서로 바뀐다.

공격팀은 정해진 타순에 따라서 타석에 선다. 9번 타자가 공을 쳤으면, 다음 타자는 1번 타자이다.

타자가 공을 쳤을 때 안타, 2루타, 3루타, 홈런, 아웃 중 하나의 결과를 얻는다. 각각을 1, 2, 3, 4, 0으로 정의한다.

감독은 어떤 타순으로 경기를 하면 가장 많은 득점을 할 수 있는지 알고 싶다. 1번 선수를 4번 타자로 미리 결정했다. 이 때, 가장 많은 득점을 구해보자.

입력

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 선수부터 9번 선수까지 순서대로 주어진다.

출력

첫째 줄에 가장 많은 득점을 출력한다.

풀이

브루트포스 + 시뮬레이션 문제이다. 8명의 타순을 순열로 만들고(1번 선수는 4번 타자 고정), 각 타순마다 야구 게임을 시뮬레이션하여 최대 점수를 구한다.

코드

from itertools import permutations

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

max_score = 0
# permutations는 애초에 중복 없음 → set() 필요 없음
for perm in permutations([i for i in range(1, 9)]):  # 1번 선수 제외 순열
    order = list(perm[:3]) + [0] + list(perm[3:])  # 0번(1번 선수) 4번 타자 고정

    score = 0
    idx = 0  # 타석 순서 인덱스
    for inning in hit_result:
        out = 0
        base1, base2, base3 = 0, 0, 0  # 각 루의 주자 (0/1)
        while out < 3:
            result = inning[order[idx]]
            if result == 0:
                out += 1
            elif result == 1:
                score += base3
                base1, base2, base3 = 1, base1, base2
            elif result == 2:
                score += base3 + base2
                base1, base2, base3 = 0, 1, base1
            elif result == 3:
                score += base3 + base2 + base1
                base1, base2, base3 = 0, 0, 1
            elif result == 4:
                score += base3 + base2 + base1 + 1
                base1, base2, base3 = 0, 0, 0
            idx = (idx + 1) % 9

    max_score = max(max_score, score)

print(max_score)

시간 복잡도

O(8! × N × 타석수) = O(40320 × 50 × 약 27) ≈ O(54,432,000)