[BOJ/Python] 1309.동물원

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

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

41

---

풀이

DP 점화식을 세우기 위해 1부터 4까지 경우의 수를 그림으로 직접 그려봐 값을 구했다.

n = 1 일 때, 1마리 x 2 + 0마리 1 = 3

n = 2 일 때, 1마리 x 4 + 2마리 x 2 + 0마리 1 = 3 = 7

n = 3 일 때, 1마리 x 6 + 2마리 x 8 + 3마리 x 2 + 0마리 1 = 17

표로 나타내면. . .

dp[i-1] * 2 + dp[i-2]의 점화식이 나온다.

정답 코드

n = int(input())
dp = [0] * 100001
dp[1] = 3
dp[2] = 7
for i in range(3, n+1):
    dp[i] = (dp[i-2] + (dp[i-1]) * 2) % 9901
print(dp[n])

-> 처음에 문제가 요구하는 바를 제대로 이해하지 못해 어려움이 있었다. 사자 수가 주어지지 않았는데 어떻게 경우의 수를 구하지? 했는데 알고 보니, 주어진 우리 칸 수에 사자 0마리, 1마리, 2마리... 다 넣어보며 되는 경우의 수를 세는 거였다.

-> indexerror의 경우, N이 1부터 시작함을 간과하고 dp 크기를 N+1로 지정해 일어났다. dp를 만들 때, 최대 범위로 만들어 두고 생각하는 편이 편한 거 같다.