백준 1309 파이썬 (동물원)

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

💻 Code

import sys
input = sys.stdin.readline

n = int(input())
dp = [ [0,0,0] for _ in range(n+1)]

for i in range(3):  # n=1일 때 값 초기화 
    dp[1][i] = 1

# [i][0] 양쪽 다 없는 경우, [i][1] 왼쪽만, [i][2] 오른쪽만
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)

3가지 경우로 나누어서 점화식을 구해야 한다

i번째 행을 추가할 때 (n이 1씩 증가할 때)
1. 사자가 왼쪽 오른쪽 둘 다 없는 경우
- i-1번째 행(바로 위의 행)은 왼쪽 오른쪽 둘 다 없거나 왼쪽만 있거나 오른쪽만 있을 수 있다.
2. 사자가 왼쪽만 있는 경우
- i-1번째 행은 왼쪽 오른쪽 둘 다 없거나 오른쪽만 있을 수 있다.
3. 사자가 오른쪽만 있는 경우
- i-1번째 행은 왼쪽 오른쪽 둘 다 없거나 왼쪽만 있을 수 있다.

따라서 점화식은
1. dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])
2. dp[i][1] = (dp[i-1][0] + dp[i-1][2])
3. dp[i][2] = (dp[i-1][0] + dp[i-1][1])

n=1 일 때 몇가지 n=2일 때 몇가지 이렇게 총 개수로 풀리지 않는다면 거기에서 경우를 더 쪼개서 생각해보는것도 방법인거 같다.