백준 야구 17281

문제이해

시작과 동시에 각 타자의 결과는 정해져있고 순번을 바꿔서 최대점수를 내는 문제이다. 3아웃시 이닝이 변경된다. 다음 예제가 조금 헷갈렸었다.

2
0 4 4 4 4 4 4 4 4
0 4 4 4 4 4 4 4 4

2 이닝 동안 9명의 선수의 타율이다. 1번 선수는 항상 4번타자이고 총 43점이 나온다. 이닝이 변경되어도 공격순서는 변하지 않으므로 타순이 4440 4444 일때 결과는 다음과 같다.

1이닝 4440 44444 4440 44444 4440 
2이닝                            44444 4440 44444 4440 44444 4440

코드

1. 초기화 문제

while loop로 3out까지 반복하는 것은 좋았다. 다만 이닝이 변경되어도 타순이 그대로 유지되어야하는데 아래 코드에서는 이닝이 변경되면 for c in cands에서 타순이 0번으로 초기화된다.

score = 0
for e in range(N): # einnings

    out_count = 0
    attackers = []
    while out_count< 3:

        for c in cands:
            state = board[e][c]

            if state == 0:
                out_count +=1
            elif state == 1:
                attackers = [a+1 for a in attackers] + [1]
            elif state == 2:
                attackers = [a+2 for a in attackers] + [2]
            elif state == 3:
                attackers = [a+3 for a in attackers] + [3]
            else:
                attackers = [a+4 for a in attackers] + [4]

            for at in attackers:
                if at > 3:
                    score +=1
                attackers.remove(at)

이닝이 끝나면 이전 타순을 유지해야하는데 해당 코드에서는 while loop에서 이닝이 변한후 타순을 초기화 하고 있는 실수를 했다.

2. 시간초과 문제

List에서 shift연산 구현이 난해해서 출루한 타자들을 리스트로 관리하려고 했다. 그리고 안타가 나올때 마다 기존의 타자들의 위치를 1씩 증가시키고 3이 넘으면 홈에 들어온걸로 간주하여 점수를 1씩 증가시켰다.

하지만 공교롭게도 매 공격마다 타자들의 위치를 찾고, 갱신하고, 추가하는 것은 시간이 오래 걸렸다.

from itertools import permutations

max_scores=[]
availables = permutations(range(1,9), 8)

for __cands in availables:
    _cands = list(__cands)
    cands = _cands[0:3] + [0] + _cands[3:]

    score = 0
    idx = 0
    for e in range(N): # einnings

        out_count = 0
        attackers = []


        while out_count< 3:
            idx = idx%9

            
            state = board[e][cands[idx]]

            if state == 0:
                out_count +=1
            elif state == 1:
                attackers = [a+1 for a in attackers] + [1]
            elif state == 2:
                attackers = [a+2 for a in attackers] + [2]
            elif state == 3:
                attackers = [a+3 for a in attackers] + [3]
            else:
                attackers = [a+4 for a in attackers] + [4]

            for at in attackers:
                if at > 3:
                    score +=1
                attackers.remove(at)

            # print('eining', e, 'idx',idx,'state',state, attackers, 'score',score)
            idx += 1

    # quit()
    max_scores.append(score)

print(max(max_scores))        

* 완성.

shift 연산을 아주 간단하게 만들 수 있었다. 그냥 변수 2~3개를 직접 선언해서 직접 관리하면 된다.

max_scores=[]
availables = permutations(range(1,9), 8)

for __cands in availables:
    _cands = list(__cands)
    cands = _cands[0:3] + [0] + _cands[3:]

    score = 0
    idx = 0
    for e in range(N): # einnings

        out_count = 0
        base1,base2,base3= 0,0,0

        while out_count< 3:
            idx = idx%9

            state = board[e][cands[idx]]
            idx += 1
            if state == 0:
                out_count +=1
            
            elif state==1:
                score += base3
                base1,base2,base3 = 1, base1, base2
            elif state==2:
                score += (base2+base3)
                base1,base2,base3 = 0, 1, base1
            elif state ==3:
                score += (base1+base2+base3)
                base1,base2,base3 = 0,0,1
            else:
                score += (base1+base2+base3+1)
                base1,base2,base3 = 0,0,0
    max_scores.append(score)
print(max(max_scores))          

요약

1. 자나깨나 변수 초기화 조심!!
2. 변수 3개 이하의 Shift 연산 구현.