[문제 바로가기] https://www.acmicpc.net/problem/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
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
💡 문제 풀이
시간초과로 고생한 문제...
문제를 구현하는 것은 그렇게 어렵지 않았다.
일단, 타자 순서를 고르는게 핵심이기 때문에 어떻게 해결할지 생각해보았다.
아무리 생각해보아도 탐욕법(Greedy)은 아닌 것 같아서 순열을 이용한 완전탐색으로 최대 점수를 구하고자 했다.
순열은 permutations 함수를 사용하였다.
이 때, 주의할 점은 1번선수를 4번타자로 고정했다는 점이다.
따라서 선수들의 순서를 0부터 8까지(9명의 선수) 번호를 부여했을 때 0번은 항상 1번선수가 되어야 한다.
step 1)
permutations를 이용하여 range(1, 9)에 해당하는 순열을 만든다.
이 때, 1번 선수가 4번타자가 되야하는 조건은 3번째 인덱스에 '0'을 추가함으로서 해결하였다.
→ 1번선수(0번 인덱스)는 항상 4번타자(3번째에 위치)해야 하기 때문
step 2)
이후, 주어진 순서대로 게임을 마무리했을 때 나오는 최대 점수를 구하는 과정은 solve 함수로 구현하였다.
- score : 주어진 순서대로 게임을 마무리했을 때 얻는 점수
- idx : 선수 순서(인덱스)
야구에서 1루, 2루, 3루를 표현해야하는데 처음에는 deque를 이용해서 pop, push로 구현하였는데 시간초과가 났었다...
이후 불필요한 변수, 자료구조 사용을 지양해야 파이썬이 통과된다는 글을 참고하여 '베이스'는 변수 3개를 사용하여 간단하게 표현하였다.
- base1 / base2 / base3 : 1, 2, 3루 베이스
각 이닝마다 주어진 순서대로 게임을 진행하는데 아웃 카운트가 3개가 나오면 해당 이닝은 마쳐야한다.
- out : 아웃 카운트
게임이 진행되면서 안타, 2루타, 3루타, 홈런, 아웃에 대해서 변수를 초기화하고 점수를 계산한다.
step 3)
순열을 이용하여 모든 경우의 수를 다 따져보았을 때 가장 큰 점수를 answer 변수에 최신화하여 출력한다.
import sys
from itertools import permutations
def solve(li):
score = 0
idx = 0
for play in players:
base1, base2, base3 = 0, 0, 0
out = 0
while out < 3:
if play[li[idx]] == 0:
out += 1
elif play[li[idx]] == 1:
score += base3
base1, base2, base3 = 1, base1, base2
elif play[li[idx]] == 2:
score += (base2 + base3)
base1, base2, base3 = 0, 1, base1
elif play[li[idx]] == 3:
score += (base1 + base2 + base3)
base1, base2, base3 = 0, 0, 1
elif play[li[idx]] == 4:
score += (base1 + base2 + base3 + 1)
base1, base2, base3 = 0, 0, 0
idx = (idx+1) % 9
return score
N = int(sys.stdin.readline())
players = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
answer = 0
for li in permutations(i for i in range(1, 9)):
answer = max(answer, solve(list(li[:3]) + [0] + list(li[3:])))
print(answer)자료구조, 변수생성에서도 시간초과를 발생시키는 요소가 존재했지만
이번에도 입력부분에서 sys.stdin.readline()을 사용해야 했었다.
백준에서는 sys.stdin.readline()을 필수로 사용해야하나보다...😩
