[baekjoon] 백준 1309번(파이썬): 동물원

문제

1309번: 동물원

알고리즘

- n번째 우리의 사자가 없는 경우와 왼쪽에 있을 경우, 오른쪽의 있을 경우를 나눠서 문제를 수행한다.

- n번째 우리의 사자를 배치하는 경우의 수의 합을 출력한다. 

코드

import sys

n = int(sys.stdin.readline())

dp = [[0, 0, 0] for _ in range(n + 1)]
dp[1][0], dp[1][1], dp[1][2] = 1, 1, 1 # n = 1일 때, 3가지 경우의 수

# 점화식 : n번째 우리의 사자가 없는 경우와 왼쪽에 있을 경우와 오른쪽의 있을 경우로 나눠서 수행
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) # n번째 우리의 사자를 배치하는 경우의 수의 합을 출력

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법