백준 | 동물원

백준 동물원

import sys


n = int(sys.stdin.readline().strip())
dp = [[0, 0, 0] for _ in range(n + 1)]

# dp[i][0]: i번째 줄에 사자를 배치하지 않은 경우의 배치 수
# dp[i][1]: i번째 줄의 왼쪽에 사자를 배치한 경우의 배치 수
# dp[i][2]: i번째 줄의 오른쪽에 사자를 배치한 경우의 배치 수

# 첫째 줄에 사자 배치
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)