[백준 1309 동물원 문제] PYTHON

 

DP 문제는 규칙을 찾을 수 있으면 쉽다.

우선 N=1일때 2일때 ~ 이런식으로 N=4일때까지의 값을 계산해봤다.

결국 i[N]= i[N-2]+i[N-1]*2 라는 규칙을 찾을 수 있었다.

 

N = int(input())
dp = [1, 3]
for i in range(2, N+1):
    dp.append((dp[i-1]*2+dp[i-2]) % 9901)
print(dp[-1])