[Python] boj no. 1309 : 동물원

Problem

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

Idea

N번째 행의 우리에 사자를 넣지 않는 경우, 왼쪽 우리에 사자를 넣는 경우 그리고 오른쪽 우리에 사자를 넣는 경우로 나누어 동적 계획법을 이용하여 해결하였다.

1. N-1번째에서 사자를 우리에 넣지 않는 경우 N번째의 모든 경우에 포함.
2. 왼쪽 우리에 사자를 넣는 경우, N-1번째에서 오른쪽 우리에 사자를 넣는 경우를 포함.
3. 오른쪽 우리에 사자를 넣는 경우, N-1번째에서 왼쪽 우리에 사자를 넣는 경우를 포함.

Code

N = int(input())

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

Comment