[python] 백준 17281 야구

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

17281번: ⚾

 

문제 해결

• 야구 규칙이 있고 각 이닝에 칠 수 있는 타구를 타자마다 알 수 있을 때 최고의 차순일 때 득점할 수 있는 득점 값 구하기
• 사실 permutations(순열)을 쓰기 부담스러웠다. (당연히 시간복잡도가 크기 때문...)
• 하지만 다른 방법이 없다는 것을 알았고 각 경우 득점은 시물레이션을 통해 값을 얻도록 해야한다.
• 타자의 기록은 베이스 이동으로 결과를 기록할 수 있다. 1,2, 3, 베이스 주자 유무로 어떤 타구냐에 따라 주자 이동을 알 수  있기 때문이다.

 

CODE

import sys
input = sys.stdin.readline
def permutations(arr, n):
    result = []

    if n == 0:
        return [[]]

    for i, elem in enumerate(arr): 
        for P in permutations(arr[:i] + arr[i+1:], n-1):
            result += [[elem]+P]
              
    return result
def solve(line_up):
    now = 0
    score = 0
    for e in I:
        o = 0
        b1, b2, b3 = 0, 0, 0 # base 1루, 2루 3루 유무 0/1
        while o<3:
            if e[line_up[now]] ==0:
                o += 1
            elif e[line_up[now]] ==1:
                score += b3
                b1,b2,b3 = 1, b1,b2
            elif e[line_up[now]] ==2:
                score += (b2+b3)
                b1, b2, b3 = 0,1,b1
            elif e[line_up[now]] ==3:
                score += (b1+b2+b3)
                b1, b2, b3 = 0, 0, 1
            else:
                score += (b1+b2+b3+1)
                b1, b2, b3 = 0, 0, 0
            now = (now+1)%9
    return score
if __name__=='__main__':
    n = int(input())
    I = [list(map(int, input().split())) for _ in range(n)]
    answer = 0
    for line_up in permutations([i for i in range(1,9)],8):
        line_up = list(line_up[:3])+[0]+list(line_up[3:])
        answer = max(answer,solve(line_up))
    print(answer)