[Python] 동물원 - 백준 (DP)

해당 글은 백준 1309번 문제 '동물원'을 다룬다.

문제

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

1309번: 동물원

 

설명

해당 문제는 DP 문제이고, 9901로 나눈 나머지를 출력하라는데서도 힌트를 얻을 수 있다.

그리고 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정하는 조건이 있다.

한 마리도 배치하지 않았을 경우(X), 왼쪽에 배치할 경우(L), 오른쪽에 배치할 경우(R)를 고려한 (n+1)x3의 배열을 생성하고, 아래의 점화식을 통해 해결할 수 있다.

1) i번째 행이 X일 경우, i-1번째 행은 X, L, R 모든 경우가 올 수 있으므로 이들의 합을 넘겨준다.

2) i번째 행이 L일 경우, i-1번째 행은 X, R의 경우가 올 수 있으므로 이들의 합을 넘겨준다.

3) i번째 행이 R일 경우는 반대로, i-1번째 행은 X, L의 경우가 올 수 있으므로 이들의 합을 넘겨준다.

 

 

코드

import sys

input = sys.stdin.readline
n = int(input())
dp = [[0] * 3 for _ in range(n + 1)]
dp[1] = [1, 1, 1]  # X, L, R
for i in range(2, n + 1):
    dp[i][0] = sum(dp[i - 1]) % 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)