[백준] 1309 동물원 with Python

📌 BOJ 1309 동물원

💡 조건

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

2. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.

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

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

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

6. DP, 다이나믹 프로그래밍 유형의 문제

🖥 소스 코드

from sys import stdin

n = int(stdin.readline())
dp = [0 for _ in range(100001)]
dp[1], dp[2], dp[3] = 3, 7, 17

for i in range(4, 100001):
    dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901

print(dp[n])

🔖 예제 및 실행결과

예제

4

실행결과

41

⌨️ 문제 풀이

1. n의 크기가 최대 10만이며, 2 * N 배열에 사자를 배치할 수 있는 경우를 구해야하며, 사자를 배치하는 경우의 수를 9901로 나누어야한다.

2. 이러한 문제는 N의 크기가 크고, 경우의 수를 구해야하기 때문에 브루트포스 같은 알고리즘으로 해결하려고 하면 시간초과가 발생한다.

3. 그렇기 때문에 우리가 생각할 수 있는 알고리즘은 다이나믹 프로그래밍이 있겠다.

4. n 이 1일 때는 1 * n = 2. 세가지의 경우가 있다.
   n 이 2일 때에는 7가지, n 이 3일 때에는 17가지가 된다.

5. 이를 통해서 dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901 라고 할 수 있다.

6. 이를 통해서 dp list 를 채워 입력으로 받은 n에 해당하는 경우의 수를 출력하며 된다.