백준 문제 중 1309번, DP, ‘동물원d’

백준 문제 중 1309번

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

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

---

풀이

우선 예시를 몇개 살펴보자.

n = 1 일때 2 × 1의 우리에 사자를 넣는 방법은
[0,0], [0,1], [1,0]
3개 이다.

n = 2 일때 2 x 2의 우리에 사자를 넣는 방법은 [0,0][0,0], [0,0][0,1], [0,0][1,0]
[0,1][0,0], [0,1][1,0]
[1,0][0,0], [1,0][0,1]
7개 이다.

2 x n크기의 우리에 사자를 넣을때 맨 마지막 n번째 우리에 사자를 넣는 방법을 각각 [0,0] [0,1] [1,0] 이라 할때 각 방법을 0,1,2 로 인덱스로 하고 2 x n크기에서 방법의 수를 값으로 하는 배열을 dp라 하자,그러면 dp[n][0]은 dp[n-1] 중 다음이 [0,0]로 끝날 수 있는 값을, dp[n][1]은 dp[n-1]중 다음이 [0,1]로 끝날 수 있는 값을, dp[n][2]은 dp[n-1]중 다음이 [1,0]로 끝날 수 있는 값을 나타낸다.

이를 수도코드로 표현하면

dp[n][0] = sum(dp[n-1])

dp[n][1] = dp[n-1][0] + dp[n-1][2]

dp[n][2] = dp[n-1][0] + dp[n-1][1]

이되고 이를 코드로 구현하면 아래와 같다.

n = int(input())

M = 9901

dp = [[0,0,0] for _ in range(n)]

 # 2 x 1 의 방법 각각 [0,0], [0,1], [1,0]는 1개씩이다.
dp[0][0], dp[0][1], dp[0][2] = 1,1,1

for i in range(1,n):
    # int 가 2^31-1을 넘는걸 방지하기위해 %M 를 추가
    dp[i][0] = sum(dp[i-1])%M
    dp[i][1] = (dp[i-1][0] + dp[i-1][2])%M
    dp[i][2] = (dp[i-1][0] + dp[i-1][1])%M

print(sum(dp[n-1])%M)

4
41