[백준] 1309번 동물원 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1 (연습)

---

---

---

💡 문제

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

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

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

입력

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

출력

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

---

💭 접근

이 문제의 경우 우리의 크기(n)이 증가할 때마다 사자를 배치할 수 있는 경우의 수를 구하면 된다. 이때 마지막에 붙은 우리를 00, 01, 10 라고 가정해보자. (1은 사자가 있는 경우 0은 없는 경우)

1. 00 우리가 붙는 경우 : 이 경우엔 모든 경우에 붙을 수 있다.
   -> 00 우리의 수 + 01 우리의 수 + 10 우리의 수
2. 01 우리가 붙는 경우 : 이 경우엔 01을 제외한 모든 우리에 붙을 수 있다.
   -> 00 우리의 수 + 10 우리의 수
3. 10 우리가 붙는 경우 : 이 경우엔 10을 제외한 모든 우리에 붙을 수 있다,
   -> 00 우리의 수 + 01 우리의 수

이를 테이불로 알아보자.

n	00	01	10	총합
1	1	1	1	3
2	3	2	2	7
3	7	5	5	17
4	17	12	12	41
...	...	...	...	...

이를 보았을 때 점화식을 아래와 같이 도출할 수 있다.

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

---

🔥 내가 작성한 코드

n = int(input())
dp = [[1, 1, 1] for _ in range(n)]

for i in range(1, n):
    dp[i][0] = sum(dp[i - 1]) % 9901
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901

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

---

📒 코드

n = int(input())
dp = [1, 3]

for i in range(2, n + 1):
    dp.append((2 * dp[i - 1] + dp[i - 2]) % 9901)

print(dp[n] % 9901)

위에서 구한 점화식을 정리하면 정답은 이렇게 구할 수 있다.

sum(dp[i]) ->
dp[i - 1][0] + 2 x (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])
-> 2 x dp[i - 1] + dp[i - 2]

---

💭 후기

문제를 크게 전체적으로 봤을 때 해결이 어렵다면 각각의 케이스로 나누어 보는 것도 좋은 방법인 것 같다.

---

🔗 문제 출처

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

---