[BOJ] 1309번 동물원 문제 - Python

www.acmicpc.net/problem/1309

1309번: 동물원

 

생각보다 어려웠다..

 

 

 

k번째 행에 대한 경우는 다음과 같다.

 

1. k번째 행에 사자가 없는 경우

이는 사실 k-1번째 경우의 수와 같다.

k번째 행만 빼고 전부 다 배치하는 건 k-1번까지만 배치하는 것과 같다.

 

2. k번째 행의 왼쪽에 사자가 있는 경우

이는 k-1번째 경우에서 k-1번째 행의 왼쪽에만 사자가 없는 경우와 같다.

당장 내 바로 위에만 사자가 없으면 얼마든지 배치할 수 있기 때문이다.

 

3. k번째 행의 오른쪽에 사자가 있는 경우

2의 경우와 같다.

 

 

그럼 다음과 같이 풀이하면 된다.

 

두 개의 배열은 선언한다.

 

각각 dp1과 dp2라고 한다면, dp1에는 k번째 행까지 배치할 수 있는 경우를 담고, dp2에는 k번째 행의 왼쪽(혹은 오른쪽)에 사자를 배치하는 경우를 담는다.

 

 

결과부터 얘기하면 다음과 같다.

dp2[k] = dp1[k-1] - dp2[k-1]

dp1[k] = dp1[k-1] + 2*dp2[k]

 

 

dp1에서 dp2를 빼주는 것은 전체의 경우에서 마지막 열의 왼쪽(혹은 오른쪽)에 사자가 있는 경우를 빼는 것

즉, k-1번째 열의 왼쪽에 사자가 없는 경우를 의미한다.

 

 

N = int(input())

dp1 = [1] * (N+1)
dp2 = [0] * (N+1)

for i in range(1, N+1):
    dp2[i] = (dp1[i-1] - dp2[i-1]) % 9901
    dp1[i] = (dp1[i-1] + 2*dp2[i]) % 9901

print(dp1[N])