[백준] 1309번 동물원

💡문제접근

• 다이나믹 프로그래밍 = 규칙성

💡코드(메모리 : 35108KB, 시간 : 108ms)

import sys
input = sys.stdin.readline

N = int(input().strip())

dp = [1 for _ in range(100001)]
dp[1] = 3
dp[2] = 7
for i in range(3, N+1):
    dp[i] = (dp[i-2] % 9901) + ((dp[i-1] * 2) % 9901)
print(dp[N] % 9901)

💡소요시간 : 5m