백준 1309번 파이썬 문제풀이(DP - 동물원)

---

이 문제의 풀이방식은 2가지가 있다. 우선 첫번째는 무식하게 N이 0일때부터 구해보는 것이다. 문제에서 하나도 배치하지 않는 경우도 1이라고 했기에 DP[0] =1 그 이후 타일을 그려보면서 구했다. DP[1] = 3,  DP[2]=7, DP[3] = 17 .. 여기서 규칙하나를 발견했다. DP[i] = DP[i-2] + DP[i-1] * 2 이다.

 

꽤나 쉽게 구해서 이렇게 쉽게 풀 문제가 아닌데 라고 생각하면서 정답을 봤더니 역시나 조건을 분기하여 경우의 수로 구하는 것이었다.

 

DP = [[0 , 0 , 0] ,....] 와 같이 DP에 2중리스트로 우선 저장한다.

그 이유는 DP[i][0] 값에는 이전 타일의 왼쪽에 사자들이 있는 경우

DP[i][1] 은 이전 타일의 오른쪽에 사자들이 있는 경우 DP[2]는 이전 타일에 사자들이 없는 경우 이렇게 3가지를 나누어 놓고 구하는 것이었다.

 

사자들이 이전 타일의 왼쪽에 있는 경우는 DP[i-1][0] = DP[i-1][1] + DP[i-1][2] 가 된다. 그 이유는 왼쪽에 사자들이 있다면 오른쪽타일과 사자들이 없는 경우만 사자들이 올 수 있기 때문이다. 이와 같이 점화식을 만들면 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
#dp[1] 값을 1로 만들기 위해 1로 초기화
dp = [[1, 1, 1] for _ in range(N + 1)]

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

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