[실버1] 1309번 : 동물원

🛠 문제

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

👩🏻‍💻 해결 방법

n줄에 사자를 하나도 배치하지 않을 경우의 수, n줄 왼쪽에 사자를 배치할 경우의 수, n줄 오른쪽에 사자를 배치할 경우의 수를 합산하여 구할 수 있었다

소스 코드

n = int(input())

dp = [[0, 0, 0] for _ in range(n+1)]
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)