[🥈1 / 백준 1309 / 파이썬] 동물원

 

1309번: 동물원

 

문제

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

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

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

입력

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

출력

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

 

예제 입력  4

예제 출력  41

 

풀이

 

n = 0 일 때, 사자를 놓지 않는 경우도 하나의 수로 가정한다고 했으므로 경우의 수는 1이 된다.

 

n = 1 일 때

 

위와 같은 방법으로 사자를 둘 수 있다. 즉, 경우의 수는 3이다.

 

 

n = 2 일 때를 생각해보자.

 

사자를 놓지 않는 방법은, n=1 일때 나올 수 있는 경우의 수만큼 둘 수 있다. 즉, 3이 된다.

사자를 왼쪽 혹은 오른쪽에 두는 방법은 총 4가지가 있음을 쉽게 유추할 수 있다.

 

따라서, n=2 일때 경우의 수는 7이다.

 

 

규칙이 보인다.

 

사자가 없는 경우 3가지 수 아무거나 가능하다. 사자가 있는 경우 빈 우리 혹은 반대 방향으로 둘 수 있다.

 

즉, 현재 우리에서 사자가 있는 우리와 없는 우리로 분리한 뒤빈 우리의 수 × 3 + 사자가 있는 우리 × 2 를 하면 되는 것이다.즉, 점화식은 다음과 같다.

 

dp[i] = (dp[i-2]*3 + (dp[i-1]-dp[i-2])*2)

 

위 점화식을 풀어서 정리하면 다음과 같다.

 

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

 

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