백준 1309 [동물원] 파이썬

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

1309번: 동물원

N = int(input())
dp = [0, 3, 7]

for k in range(3, N+1):
    dp.append((dp[k-1]*2+dp[k-2])%9901)

print(dp[N])

dp[k-1]에는 k-1번째의 경우에 따라 칠할지 말지를 정할 수 있으므로,  x2를 해준다.

dp[k-1], dp[k-2] 모두 아예 안칠하는 경우도 존재하므로, dp[k-2]를 더해준다.