[BOJ/백준] 1309번 동물원 (Python 파이썬)

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

1309번: 동물원

 

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

41

 

---

풀이

우선 문제를 정리하면, 2*N 배열의 우리가 주어지고, 여기에 사자를 넣는 경우의 수를 구하는 것입니다. 단, 두 사자는 옆과 위 아래로 우리가 겹치면 안되고, 사자를 한 마리도 안 넣는 것도 하나의 경우의 수로 쳐야 합니다.

이제 점화식을 찾아보겠습니다.

점화식을 찾는 과정은 대략 아래와 같습니다.

N = 1
-> 1 + 2 = 3

N = 2
-> 1 + 4 + 2 = 7  
=> 2 x (N-1) 배열의 우리에서 2x1 우리를 추가할 때
새로운 사자를 (1) 놓는다. (2) 놓지 않는다.
(1) = 3
(2) = 2 + 2

N = 3
-> 1 + 6 + 8 + 2 = 17
(1) = 7
(2) = 5 + 5
여기서 5 = (dp[i-1] - dp[i-2])/2

따라서 점화식 : dp[i] = dp[i-1] + 2*{dp[i-2] + (dp[i-1]-dp[i-2])/2}
= 2dp[i-1] + dp[i-2]

 

그림을 그려서 살펴보면,

위 그림상 빨간색 박스는 "새로운 우리에 사자를 배치하지 않는 경우의 수"입니다.

즉, dp[i-1]과 같죠.

그리고 파란색 박스 하나를 계산하면, 형광색으로 구분한 수를 살펴보시면 아래와 같이 정리됩니다.

파란색 박스 = dp[i-2] + (dp[i-1] - dp[i-2])/2

dp[i] = 빨간색 박스 + 2*파란색 박스 이므로, 아래와 같이 정리됩니다.

dp[i] = dp[i-1] + 2*{dp[i-2] + (dp[i-1]-dp[i-2])/2}
= 2dp[i-1] + dp[i-2]

 

따라서, 이를 구현하면 아래와 같이 됩니다.

Code

# 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다
from sys import stdin
N = int(stdin.readline())

if N == 1:
    print(3)
else:
    dp = [1 for _ in range(N+1)]
    dp[1], dp[2] = 3, 7
    for i in range(3, N+1):
        dp[i] = (2*dp[i-1] + dp[i-2]) % 9901
    print(dp[N])