[ 백준 17281 ] ⚾ - Python

문제 보기

[사용한 알고리즘]

완전 탐색(브루트 포스), 순열

 

[문제 접근]

1번 선수를 제외한 8명(2~9번) 선수의 가능한 타순을 모두 수행해야만 아인타팀이 얻을 수 있는 최대 점수를  알아낼 수 있습니다. 따라서 가능한 타순은 순열을 통해 파악하였으며, 얻은 순열 값들을 완전 탐색하였습니다.

 

[알고리즘]

1. 순열을 통해 타순을 구합니다.

2. 해당 타순으로 N 이닝을 수행한 점수를 구합니다.

3. 위 과정을 가능한 모든 타순에 대해 수행하고 최대 점수를 출력합니다.

 

[주의할 점]

Python3로는 통과한 사람이 없었으며 pypy3도 시간 초과를 위해서 고려할 부분이 많았습니다.

저는 시간 초과를 해결하기 위해서 2가지를 고려하였습니다.

- 1, 2, 3루 베이스 정보를 배열이 아닌 변수 값을 사용하였습니다.

- 함수를 호출하는 시간을 단축하기 위해서 모든 코드를 main 문 작성하였습니다.

 

[코드]

import sys
from itertools import permutations


if __name__ == "__main__":
    n = int(sys.stdin.readline())  # 이닝 수
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    people = [1, 2, 3, 4, 5, 6, 7, 8]
    answer = 0
    for turn in permutations(people, 8):
        turn = list(turn)
        turn = turn[:3] + [0] + turn[3:]
        score = 0
        index = 0
        for inning in range(1, n + 1):
            out_cnt = 0  # 아웃 카운트
            base_1, base_2, base_3 = 0, 0, 0  # 1, 2, 3루 주자
            while out_cnt < 3:
                if data[inning - 1][turn[index]] == 0:
                    out_cnt += 1
                elif data[inning - 1][turn[index]] == 1:
                    score += base_3
                    base_1, base_2, base_3 = 1, base_1, base_2
                elif data[inning - 1][turn[index]] == 2:
                    score += (base_2 + base_3)
                    base_1, base_2, base_3 = 0, 1, base_1
                elif data[inning - 1][turn[index]] == 3:
                    score += (base_1 + base_2 + base_3)
                    base_1, base_2, base_3 = 0, 0, 1
                elif data[inning - 1][turn[index]] == 4:
                    score += (base_1 + base_2 + base_3 + 1)
                    base_1, base_2, base_3 = 0, 0, 0
                index += 1
                if index == 9:
                    index = 0
        answer = max(answer, score)  # (타자 순서, 현재 타자 번호, 득점)
    print(answer)