[파이썬] 백준 1309 동물원

dp 문제인건 파악을 했으나, 전체적으로 안보고 한 경우 안에서만 규칙을 찾으려고 했다. 전체적으로 보는 연습을 해야할 것 같다.

from collections import deque
import sys
import math
 
 
a = int(input())
 
 
 
dp = [0] * (a+1)
 
dp[0]=1
dp[1]=3
 
for i in range(2,len(dp)):
 
    dp[i] = (dp[i-2]+dp[i-1]*2)%9901
 
print(dp[-1])