백준 구현 대비 야구게임

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

접근

초기 접근

순서 배열을 [1,2,3,0,4,5,6,7,8] 로 고정하고 각 이닝에서 얻는 결과를 permutations 하여 계산하고자 함. 하지만 그렇게 하면 각 이닝이 끝났을때 그 다음 타자를 계산하는데 문제상황이 생김. 그래서 이 방법은 탈락

두번째 접근

두번째 접근은 이닝 결과를 고정하고, 배열 [1,2,3,4,5,6,7,8] 을 permutations 하고, 3번째 index에 0을 삽입하여 순서 경우의 수 배열을 생성함. 이렇게 하면 다음 타자 순서 계산이 가능하게됨, 그 후 점수계산은 덱을 생성하여 1루타면 0삽입, 2루타면 0,1 삽입, 3루타면 0,1,1삽입, 4루타면 0,1,1,1을 삽입해준후 인덱스 3이상의 덱의 데이터 중 0의 갯수를 계산해주었다. 그 결과 어느정도 예상은 했지만 시간초과

세번째 접근

1) 덱을 사용하면 시간초과가 발생하여 안타를 쳤을때마다 그떄 그때 점수를 계산해주기로함. 조건문을 사용해서 점수를 계산하였음 하지만 각 타수마다 조건문을 걸어주니 또 시간초과가 발생함 ㅠ

2) 각 베이스의 상태를 기준으로 점수 계산. 그 결과 다음과 같이 최종 코드가 완성됨

최종코드

from itertools import permutations
from collections import deque
N=int(input())
answer=0
order=[1,2,3,4,5,6,7,8]
order_perm=list(permutations(order, 8))

inning=[]
for i in range(N):
  inning.append(list(map(int ,input().split())))


for pe in order_perm:     
  pe=list(pe)
  pe.insert(3,0)
  total=0
  index=0
  for i in range(N):    
    out=0
    ro=deque()
    b1,b2,b3=0,0,0     
    while True:
      if inning[i][pe[index]]==0:
        out+=1
      elif inning[i][pe[index]]==1:
        total+=b3
        b1,b2,b3=1,b1,b2

      elif inning[i][pe[index]]==2:
        total+=b3+b2
        b1,b2,b3=0,1,b1

      elif inning[i][pe[index]]==3:
        total+=b1+b2+b3
        b1,b2,b3=0,0,1


      elif inning[i][pe[index]]==4:
        total+=b1+b2+b3+1
        b1,b2,b3=0,0,0


      index=(index+1)%9

      if out==3:
        break
  answer=max(answer,total)

print(answer)