🥇 17281 ⚾️
문제
주어진 N 이닝 동안 게임을 진행
한 이닝에 3아웃이 발생하면 이닝은 종료
모든 이닝을 시작하기 전 순서는 정해지고 나중에 바꿀 수 없다.
만약 1번 타자부터 9번 타자까지 모든 타자가 공을 다 쳤는데도 3아웃이 발생하지 않았다면 이닝은 종료되지 않고 1번 타자부터 3아웃할 때까지 계속 진행한다.
3아웃 발생 시 전 이닝의 마지막 타자 다음 타자가 다음 이닝의 첫 타자가 된다.
ex) 2 이닝에 6번 타자가 마지막 타자 -> 3 이닝에 7번 타자가 첫 타자
타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.
- 안타: 타자와 모든 주자가 한 루씩 진루한다.
- 2루타: 타자와 모든 주자가 두 루씩 진루한다.
- 3루타: 타자와 모든 주자가 세 루씩 진루한다.
- 홈런: 타자와 모든 주자가 홈까지 진루한다.
- 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
입력
첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.
- 안타: 1
- 2루타: 2
- 3루타: 3
- 홈런: 4
- 아웃: 0
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
분석
야알못이라 문제를 이해하는데 꽤 오래걸렸던 같다.
예제 입력 3번을 설명해보자면,
2
0 4 4 4 4 4 4 4 4
0 4 4 4 4 4 4 4 41번 선수는 항상 4번 타자로 들어가기 때문에, 2, 3, 4, 1, 5, 6, 7, 8, 9 의 경우를 생각해보면 된다.
이 순서대로 이닝 결과를 다시 나열해 보면,
4 4 4 0 4 4 4 4 4가 되고
1 이닝에서 3 아웃될 때까지의 점수는 8 + 8 + 3(3아웃 전까지 계산) = 19가 되고
2 이닝은 5번 타자가 첫 타자가 되므로 8 + 8 + 8 = 24가 되므로 총 43점이 된다.
처음에는 deque로 maxlen=3을 고정해두고 풀이하였으나 시간 초과가 나서 배열로 바꾸어 풀었다ㅠㅠ pop()하고 appendleft()를 여러번 하게 되니 당연한 결과인 것 같다..
소스 코드
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input()) # 이닝 수
results = [list(map(int, input().split())) for _ in range(N)]
# 0번(1번)은 4번 타자 고정
answer = 0
for order in list(permutations([1, 2, 3, 4, 5, 6, 7, 8], 8)):
order = list(order)[:3] + [0] + list(order)[3:]
cnt = 0 # 홈으로 나간 선수들 수 + 1
idx = 0 # 매 이닝 마다 첫 타자
for result in results: # 이닝마다 예측한 결과들
base = [0, 0, 0] # 타자가 있는 위치에는 1 없으면 0
out = 0 # 3이 되면 이닝 종료, 이닝마다 리셋
while out < 3:
hitter = order[idx] # 현재 타자, result[hitter]는 현재 타자의 이닝 결과
idx = (idx + 1) % 9
if result[hitter] == 0: # 아웃
out += 1
elif result[hitter] == 1: # 안타
cnt += base[2]
base[0], base[1], base[2] = 1, base[0], base[1]
elif result[hitter] == 2: # 2루타
cnt += (base[2] + base[1])
base[0], base[1], base[2] = 0, 1, base[0]
elif result[hitter] == 3: # 3루타
cnt += (base[0] + base[1] + base[2])
base = [0, 0, 1]
elif result[hitter] == 4: #홈런
cnt += (base[0] + base[1] + base[2] + 1)
base = [0, 0, 0]
answer = max(answer, cnt)
print(answer)