[백준/Python] 동물원

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

 

---

DP를 사용

 

맨 위의 두 칸을 세 가지 경우로 나눈다

- 공백: 두 칸에 아무도 없음

- 좌: 왼쪽 칸에 사자 있음

- 우: 오른쪽 칸에 사자 있음

 

만약 n이 1이라면

위처럼 세 가지 경우가 있습니다

 

 

n이 2인 경우를 보겠습니다

 

그런데 아래 칸(파란색)의 경우의 수는

n=1일 때의 경우의 수와 같습니다

 

 

즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,

왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,

오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다.

 

dp 점화식으로 풀게 된다면

# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른쪽에 사자
dp[n] = [
            dp[n-1][0] + dp[n-1][1] + dp[n-1][2],
            dp[n-1][0] + dp[n-1][2],
            dp[n-1][0] + dp[n-1][1]
    	]

 

 

그런데, 이 점화식은 지난 번의 값만 있으면 되기 때문에 식이 훨씬 간결해집니다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [1, 1, 1] # 공백, 좌, 우
for _ in range(2, n+1):
    dp = [
        dp[0] + dp[1] + dp[2], 
        dp[0] + dp[2],
        dp[0] + dp[1]
    ]
    
print(sum(dp)%9901)