[Python] 백준 1309번 - 동물원

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

1309번: 동물원

 

혼자 힘으로 풀었는가? O

 알고리즘 분류
 - 다이나믹 프로그래밍

 

 

문제

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

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

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

입력

 

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

출력

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

 

---

 

규칙성을 찾기 힘들었다.

 

이 문제에서 중요한점은

 

1. 공백이 가능하다.

2. 가로 세로에 겹쳐서 못놓는다.

 

위 두가지를 유의해야 한다.

 

그림실력이 좋지않습니다.

아무튼 위와 같은 경우의 수가 존재한다.

 

1 - 3

2 - 7

3 - 17

4- 41 (입출력 예시)

 

이것만 봐선 우린 규칙성을 찾을 수 없다.

 

그래서 각 상황에 따른 표를 그려야 한다.

 

	1	2	3	4
공백	1	3	7	17
좌	1	2	5	12
우	1	2	5	12

 

이 표를 보면 이해가 될거라 생각 한다.

 

n = 1일때

공백, 좌, 우에 있는 경우의 수는 각각 3이다.

 

---

 

n = 2일때

2번째 칸에 공백이 있는 경우의 수는 3

 

2번째 칸의 좌측에 있는 경우의 수는 2

 

2번째 칸의 우측에 있는 경우의 수는 2

 

 

---

위와 마찬가지로

 

n = 3일때

 

세번째 칸에 공백이 생기는 경우의 수는 7가지는

앞의 n = 2인 경우의 수의 합과 같고

 

세번째 칸의 좌측에 잇는 경우의 수는 n=2일 때 공백 + 우측에 잇는 경우의 수를 합한 값

세번째 칸의 우측에 잇는 경우의 수는 n=2일때 공백 + 좌측에 잇는 경우의 수를 합한 값과 같다.

 

그래서 

 

	1	2	3	4
공백	1	3	7	17
좌	1	2	5	12
우	1	2	5	12

위와 같은 결과가 만들어 진다.

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [ [0 for _ in range(3)] for _ in range(n+1)]

dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, n+1):
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 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]) % 9901)