[백준] #1309 동물원 python

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

1309번: 동물원

 

📕 설명 📕

 

DP를 이용하여 풀이하였다.

 

풀이법은 알아도 와닿지는 않는다.

 

다시 풀어보기.

 

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

 

import sys
N = int(sys.stdin.readline())
dp = [0] * (N+1)
for i in range(N + 1):
    dp[i] = [0, 0, 0]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, N + 1):
    dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901

print(sum(dp[N]) % 9901)