[Python] 백준 <1309-동물원>

 

import sys
input = sys.stdin.readline

N = int(input())

if N == 1:
    print(3)
else:
    # 공식 : 2*dp[n-1] + dp[n-2]
    dp = [0]*(N+1)
    dp[1] = 3
    dp[2] = 7
    for i in range(3, N+1):
        dp[i] = (2*dp[i-1] + dp[i-2])%9901
    print(dp[N])

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