[BOJ] 17281. ⚾️(야구) (🥇, 구현)

문제

뭐 이런 문제가 다 있냐...

풀이

✔️ 타자의 순서를 정해서
✔️ 정해진 규칙을 지켜서 N번의 이닝까지 경기 진행해서
✔️ 얻을 수 있는 최대 점수를 구하면 된다

🚻 타자 순서 정하기

4번째 타자는 무조건 1번 선수여야 한다

사실 9명 타자의 순서를 다 정하면 대략 36만정도인데 1명은 이미 정해져있기 때문에 8명만 정하면 돼서 대략 4만 정도로 줄어든다

재귀를 사용해서 노가다로 구했고 당연히 시간초과ㅎㅎ

visited[0] = True
order[3] = 0
def perm(k):
    if k == 3:
        perm(4)
        return 
    
    if k == 9:
        baseball(order)
        return 

    for i in range(9):
        if visited[i] == False:
            order[k] = i
            visited[i] = True
            perm(k+1)
            order[k] = -1
            visited[i] = False

perm(0)

itertools 라이브러리의 permutations(순열)을 사용해서 1을 제외한 나머지 숫자들로 순열을 만들고 4번째 자리에 1번을 끼워넣는 방식으로 만들어야 시간초과가 나지 않음

🕐 N번째 이닝까지 경기 진행

처음엔 위에서 재귀로 순열 만드는 방식처럼 해서 타자의 순서가 다 정해지면 baseball 함수를 통해서 게임을 진행하려고 했는데 당연히 시간초과가ㅎㅎ

✔️ out이 3번 발생하면 다음 이닝으로
✔️ 다음 이닝으로 넘어가도 타자의 순서는 계속 이어져야 함

이닝이 N번을 넘길때까지 반복문으로 경기를 계속하게 된다. 이때 반복횟수가 정해져 있지 않기 때문에 while을 사용하게 됨. 아래는 각 점수별로 분기 처리.

0️⃣ 아웃 : out 1증가
1️⃣ 안타 : 1칸씩 이동, 3루 선수 점수 추가, 1루에 선수 추가
2️⃣ 2루타 : 2칸씩 이동, 2-3루 선수 점수 추가, 2루에 선수 추가
3️⃣ 3루타 : 3칸씩 이동, 1-2-3루 선수 점수 추가, 3루에 선수 추가
4️⃣ 홈런 : 4점 추가, 모든 루에 선수 없음

분기처리가 끝나면 out이 3을 넘는 경우 inning 1추가, 모든 루에서 선수 제거, out 0으로 초기화하는 세 가지 작업

최종 코드

❌ 시간초과

1, 2, 3루에 대한 정보를 담고 있는 base 배열을 가지고 각 점수에 대해서 배열 splice를 사용해서 코드를 짰는데 너무 당연하세 시간 초과가 났다 ㅎㅎ

import sys
from itertools import permutations
input = sys.stdin.readline

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

ans = 0
def baseball(order):
    global ans
    out = inning = 0
    base = [0]*3
    
    now = score = 0
    while inning < N:
        inn = arr[inning][order[now]]

        if inn == 0:
            out += 1
        elif inn == 1: 
            score += base[0]
            base = base[1:] + [1]
        elif inn == 2:
            score += sum(base[:2])
            base = base[2:] + [1, 0]
        elif inn == 3:
            score += sum(base)
            base = [1, 0, 0]
        elif inn == 4:
            score += sum(base) + 1
            base = [0, 0, 0]

        now = (now+1)%9
        
        if out == 3:
            inning += 1
            base = [0, 0, 0]
            out = 0
        
        ans = max(ans, score)

for perm in permutations(range(1, 9)):
    order = list(perm[:3]) + [0] + list(perm[3:])
    baseball(order)

print(ans)

⭕️ 정답 코드

이런 식으로 각 루에 선수가 있는지 없는지 판별하고 선수가 있는 경우에 대해서 각각의 인덱스마다 처리를 다 따로 해줘야 시간 초과가 나지 않았다.

from itertools import permutations

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

c=[1,2,3,4,5,6,7,8]
c_m=permutations(c,8)
ans = 0

for case in c_m:
    order = list(case)
    order.insert(3, 0)
    out = inning = player = score = 0
    base = [0]*3
    
    while inning < N:
        inn = arr[inning][order[player]]

        if inn == 0:
            out += 1
        elif inn == 1: # 안타
            if base[2] == 1:
                score += 1
                base[2] = 0
            if base[1] == 1:
                base[2] = 1
                base[1] = 0
            if base[0] == 1:
                base[1] = 1
            base[0] = 1
        elif inn == 2:
            if base[2] == 1:
                score += 1
                base[2] = 0
            if base[1] == 1:
                score += 1
                base[1] = 0
            if base[0] == 1:
                base[2] = 1
                base[0] = 0
            base[1] = 1
        elif inn == 3:
            if base[2] == 1:
                score += 1
                base[2] = 0
            if base[1] == 1:
                score += 1
                base[1] = 0
            if base[0] == 1:
                score += 1
                base[0] = 0
            base[2] = 1
        elif inn == 4:
            if base[2] == 1:
                score += 1
                base[2] = 0
            if base[1] == 1:
                score += 1
                base[1] = 0
            if base[0] == 1:
                score += 1
                base[0] = 0
            score += 1

        player = (player+1)%9
        
        if out == 3:
            inning += 1
            base = [0, 0, 0]
            out = 0
        
    ans = max(ans, score)
print(ans)