[알고리즘] 백준 1309 동물원

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

문제를 처음 보고는 2xn 타일링 문제와 유사하다고 생각하였다. 실제로 유사한 문제였으나 아직 점화식을 정의하는게 어려워서, 올바른 점화식을 도출하는데 어려움을 겪었다.

점화식은 다음과 같이 정의된다.

점화식

d[i][0] = i번째 칸의 왼쪽에 사자가 있을 경우
d[i][1] = i번째 칸의 오른쪽에 사자가 있을 경우
d[i][2] = i번째 칸에 왼쪽, 오른쪽 모두 사자가 없을 경우

문제에서 사자가 아예 없는 경우도 경우의 수 한 개로 계산한다고 하였으므로 기저 조건은 다음과 같이 정의 된다.

기저 조건

dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 1 # 사자가 없는 경우

먼저 dp[1]이 어떤 경우의 수를 갖는지 계산해보자.
1. dp[1]의 왼쪽 칸에 사자가 올 경우
2. dp[1]의 오른쪽 칸에 사자가 올 경우
3. dp[1]의 왼쪽, 오른쪽 모두 사자가 없다.
각각의 경우에 대해 dp[1]은 2X1의 상자이므로, 아래와 같이 결과가 나온다.

dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

그렇다면 2x2 상자인 dp[2]의 경우는 어떨까?
dp[2]는 2번째 칸의 사자의 왼쪽, 오른쪽, 없음에 대한 경우의 수를 포함하고 있다.

만약 dp[2]에서 왼쪽칸에 사자가 올 경우에는 다음과 같은 경우의 수가 가능하다.

1. dp[1]의 오른쪽에 사자가 올 경우
2. dp[1]에 사자가 없을 경우

오른쪽에 올 경우는 다음과 같다.

1. dp[1]의 왼쪽에 사자가 올 경우
2. dp[1]에 사자가 없을 경우

dp[2]에 사자가 아예 없을 경우는 다음과 같다.

1. dp[1]의 왼쪽에 사자가 올 경우
2. dp[1]의 오른쪽에 사자가 올 경우
3. dp[1]에 사자가 없을 경우

이를 바탕으로 점화식을 도출하면 다음과 같다.

dp[i][0] = dp[i-1][1] + dp[i-1][2] # 이전 칸 오른쪽, 아예 없을 경우
dp[i][1] = dp[i-1][0] + dp[i-1][2] # 이전 칸 왼쪽, 아예 없을 경우
dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] # 이전 칸 왼쪽, 오른쪽, 아예 없을 경우

이를 그대로 풀이에 적용하면 이 문제에서 AC를 받을 수 있다.

정답 코드

import sys

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

dp = [[0 for _ in range(3)] for _ in range(N+1)]

dp[0][2] = 1

for i in range(1, N+1):
    dp[i][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] + dp[i-1][2]) % 9901

print(sum(dp[N]) % 9901)