백준 #1309 - 동물원

 

문제

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

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

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

입력

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

출력

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

예제 입력

4

예제 출력

41

 

 

---

 

 

이번 문제도 dp 점화식으로 풀어야 했다.

 

동물원의 우리는 무조건 가로로 2칸이며, 가로로 붙어 있게 사자를 배치할 수 없으므로 가로 1줄에 가능한 경우의 수는 

(0, 0), (1, 0), (0, 1)의 3개이다.

 

따라서 n = 1일 때의 경우의 수는 3이 된다.

 

n = 2일 때를 보자.

2번째 줄이 (0, 0)이기 위해서는 1번째 줄의 3가지 경우의 수 모두 가능하다.

2번째 줄이 (1, 0)이기 위해서는 1번째 줄이 (0, 0)이거나 (0, 1)이어야 한다.

2번째 줄이 (0, 1)이기 위해서는 1번째 줄이 (0, 0)이거나 (1, 0)이어야 한다.

 

그렇기 때문에 최종 점화식은 다음과 같다.

 

dp[i][0] = dp[i - 1][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][1] + dp[i - 1][0]

 

 

그리고 최종 정답은 9901로 나눈 나머지를 출력해야하기 때문에 

sum(dp[n] % 9901)를 출력하였다.

 

그런데 메모리 초과가 떴다...

아무래도 맨 마지막에 9901로 나누기 때문에 중간 과정에서 너무 큰 수가 발생한 것 같다.

그래서 매 점화식마다 9901로 나누고, 그 값을 할당하는 방식으로 바꾸었더니 메모리 초과 없이 잘 작동되었다.

 

그렇게 완성한 최종 코드

 

import sys
input = sys.stdin.readline

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

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][1] + dp[i - 1][0]) % 9901

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