[Python/파이썬] 백준 28075번 스파이

28075번: 스파이

 

코드

n, m = map(int, input().split())
progress = list(map(int, input().split()))+list(map(int, input().split()))
ans = 0


def recursion(d, prev, total):
    global ans
    if d == n+1:
        if total >= m:
            ans += 1
        return
    for work in range(2):
        for place in range(3):
            if place == prev:
                recursion(d+1, place, total+progress[work*3+place]//2)
            else:
                recursion(d+1, place, total+progress[work*3+place])


recursion(1, -1, 0)
print(ans)

 

모든 경우의 수를 재귀함수로 다 계산해보며 기여도가 M 이상인 경우를 모두 구한다.

이때 같은 장소에서 임무를 진행하면 진척도가 전날의 절반이 되어야 하므로 전날 어떤 장소에서 임무를 수행했는지 체크해줄 필요가 있다.

 

처음에는 work와 place를 따로 반복문을 돌지 않고 for i in range(6)으로 하여 i%3과 prev%3이 같을 때 이전과 같은 장소에서 임무한 것으로 처리하도록 하였는데 이는 처음 prev 값이 문제가 되었다. prev가 음수 어떤 수이든 3으로 나누면 0~2 사이의 수가 나오기 때문에 오류가 발생하는 것이었다. 이걸 수정해줬더니 문제를 통과할 수 있었다.