[백준1309번] 동물원 / Python3

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

41

나의 풀이

우선 문제를 풀기위해 dp배열을 어떻게 구성할지를 생각해보았다. 일차원 배열로 N의 값에 따라 경우의 수들을 기록하면서 이전의 경우의 수들을 메모제이션을 통해 사용하면 될 것같았다. 그래서 그림을 그려보면서 점화식을 찾아냈다.

문제에서 사자를 하나도 배치하지 않은 경우도 하나의 경우의 수로 채운다고 했으니 dp[0] = 1로 초기화를 시켜두고 N이 1인경우 dp[1] = 3으로 초기화를 시켜주었다. 1인 경우에는 (1.사자가 하나도 없는 경우, 2. 왼쪽에 있는 경우, 3. 오른쪽에 있는 경우로 총 3가지이다.) 이제는 dp[0], dp[1]을 사용하여 점차적으로 dp를 구해가면 되었다. 아래 그림은 N이 2인 경우의 모든 경우들이고 그에 대하여 이전의 경우들과 어떻게 조합이 되어있는지를 나눠놓은 것이다.

1. N = 2인 곳에 아무것도 배치하지 않는 경우 => 이전 N이 1일 경우의 수 = dp[i-1]
2. N = 1인 곳에 아무것도 배치하지 않는 경우 => 전전 N인 아무것도 없을 경우의 수에 2배 = dp[i-2] * 2
3. N = 1, N = 2인 곳 모두 배치가 되는 경우 => 바로 이전 경우의 수에서 바로 전전 경우의 수를 뺀 경우의 수 
    ( 전전 경우의 수는 바로 전에 아무것도 배치가 되지 않은 경우이기 때문 )   = dp[i-1] - dp[i-2]

모든 N에 대하여 위의 경우와 같다. 따라서 점화식을 세울 수 있게되었다.

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

이렇게 점화식을 구했으니 코드로 옮기면 된다. 주의할 점은 각 dp[i]를 구할때마다 결과값을 9901로 나눈 나머지 값을 저장해야한다는 점이다.

코드

# 1309번 동물원

# main
n = int(input())

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

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