나의 풀이
import sys
input = sys.stdin.readline
n=int(input())
dp=[0]*(n+1)
dp[0]=1
dp[1]=3
for i in range(2,n+1):
dp[i]=(2*dp[i-1]+dp[i-2])%9901
print(dp[n])수행시간: 112ms
나의 풀이
dp[1]~dp[3]까지 구해다 보니 dp[3]=2*dp[2]+dp[1] 인것을 발견하여 점화식 dp[i]=2*dp[i-1]+dp[i-2]을 세워 풀어봤더니 맞았다.
정확한 풀이
2*i의 우리에 사자를 넣는 경우의 수는
(2*(i-1)의 우리에 사자를 넣는 경우 중 맨위2개의 우리중 하나엔 사자가 있는 경우의 수*2(맨위 2개)) + ( 2*(i-1)의 우리 중 맨위2개의 우리 둘다에 사자가 없는 경우의수*3(맨위2개+맨위에 사자가 없는 경우) 이다.
이는 (2(dp[i-1]-dp[i-2])+(3dp[i-2])
dp[i]=2*dp[i-1]+dp[i-2]
