[파이썬 | BOJ | 17281] ⚾

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

17281번: ⚾

문제

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.

두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.

공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.

타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.

입력

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.

• 안타: 1
• 2루타: 2
• 3루타: 3
• 홈런: 4
• 아웃: 0

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

풀이

이 문제를 풀면서 영화 마션이 생각났다.

상승선의 덮개를 비닐로 바꿔버리는 장면

시간 초과를 피하기 위해서 코드를 수정하면서, 주인공이 화성 상승선의 경량화를 위해서 최소한의 장치만 남기고 모조리 뜯어버리던 장면이 생각났다.

 

이 문제의 python3 맞았습니다는 존재하지 않는다. pypy3로도 시간초과가 매우 빡빡한 문제인만큼 조금의 시간의 낭비를 허용하지 않으므로, c나 java로 푸는게 정신건강에 좋다.

 

일단 기본적인 야구규칙을 알고 있다면 문제에서 요구하는 점수 조건을 구현하기는 쉽다. N루타마다 모든 주자가 N개의 베이스를 진행하기 때문에 3개의 베이스 변수를 생성해서 주자를 판별하고, 점수를 계산하면 된다.

 

일단 이 문제를 푸는 기본적인 아이디어는 4번 타자를 제외한 1, 2, 3, 5, 6, 7, 8, 9번 타순의 순열을 모두 시행해보고, 가장 최고의 점수를 낼 수 있는 순열을 선택하는 것이다.

 

8! = 40320이므로 쉽게 해결할 수 있을것이라 생각했는데, 각 케이스마다 50개의 이닝을 돌고, 3아웃이 될때까지 반복문이 계속 돌아가므로 시간초과가 떴다.

import sys
from itertools import permutations
from collections import deque
read = sys.stdin.readline
 
def baseball(inning):
    global maxScore
 
    hitter = 0
    score = 0
    for i in range(inning):
        # 한 이닝에서 유지되는것들
        outcount = 0
        base = deque([False, False, False])
 
        while outcount < 3:                 #3아웃이 될때까지 반복
            # 같은 타석에서 유지되는 것들
            result = results[i][order[hitter]]
 
            if result == 0:     #아웃
                outcount +=1
            else:                           #그 외의 경우
                base.appendleft(True)       #주자 하나 진출
                if base.pop():              #home에 True(주자)가 들어오면 점수 +1점
                    score += 1
                for _ in range(result-1):   #안타 이상이면 계속 주자가 돈다.
                    base.appendleft(False)  
                    if base.pop():          #home에 True(주자)가 들어오면 점수 +1점
                        score += 1
            hitter += 1                     #다음타자
            if hitter >= 9:
                hitter = 0
                
    if score > maxScore:
        maxScore = score
    
 
 
 
N = int(read())
results = []
 
# (index+1)타순에 value번 선수가 친다.
# 4번타자는 0번 선수로 고정
# 8!개의 경우의 수
 
temp = list(range(1, 9))
maxScore = -1
for _ in range(N):
    results.append(list(map(int, read().split())))
 
 
for x in permutations(temp, 8):
    order = list(x)
    order.insert(3, 0)
    baseball(N)
 
print(maxScore)

초기에 작성한 코드로, 당연히 시간초과가 났다.

 

수십번 새로 제출하면서 통과받은 코드는 다음과 같다.

일단 함수를 호출하는 것을 빼버렸고, 베이스를 나타내는 list를 각각의 변수로 바꾸었고,

최소한의 변수를 사용하였다.

 

# [파이썬 | BOJ | 17281] ⚾
import sys
from itertools import permutations
read = sys.stdin.readline
    
N = int(read())
results = [list(map(int, read().split())) for _ in range(N) ]
 
# (index+1)타순에 value번 선수가 친다.
# 4번타자는 0번 선수로 고정
# 8!개의 경우의 수
 
maxScore = -1
 
for order in permutations((range(1, 9)), 8):
    order = list(order[:3]) + [0] + list(order[3:])
    hitter = 0
    score = 0
    for i in range(N):
        # 한 이닝에서 유지되는것들
        outcount = 0
        first, second, third = 0, 0, 0
 
        while outcount < 3:                 #3아웃이 될때까지 반복
            # 같은 타석에서 유지되는 것들
            result = results[i][order[hitter]]
            
            if result == 0:     #아웃
                outcount +=1
            elif result == 1:
                score += third
                first, second, third = 1, first, second
            elif result == 2:
                score += (second + third)
                first, second, third = 0, 1, first
            elif result == 3:
                score += (first + second + third)
                first, second, third = 0, 0, 1
            elif result == 4:
                score += (first + second + third + 1)
                first, second, third = 0, 0, 0
      
            hitter = (hitter + 1) % 9                     #다음타자
    if maxScore < score:
        maxScore = score
 
print(maxScore)