[Python] BOJ / 1309번 / 동물원

1309번: 동물원

 

📝 문제

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

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

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

 

📜 풀이

• 기존 우리에 새로운 우리를 추가한다는 개념으로 생각해보자.
• 즉, 기존 2 x 2 크기였던 우리에 1 x 2 크기의 우리를 추가한다면 3 x 2 크기의 우리가 될 것이다.
• 이때 우리를 추가하는 경우의 수를 생각해보면 다음과 같은 두 종류로 나눌 수 있다.
  • 사자가 한 마리도 배치되어 있지 않은 우리를 추가하는 경우
  • 사자가 왼쪽 또는 오른쪽에 배치되어 있는 우리를 추가하는 경우
• 먼저 첫 번째의 경우는, 추가되는 우리에 사자가 한 마리도 배치되어 있지 않기 때문에 그 이전 크기의 우리의 마지막 행에 사자가 어떤 식으로 배치되었든 상관없이 우리를 추가할 수 있다.
• 두 번째의 경우는, 추가되는 우리의 왼쪽 또는 오른쪽에 사자가 한 마리 배치되어 있기 때문에, 우리를 추가하기 위해서는 그 이전 크기의 우리의 마지막 행에 사자가 한 마리도 배치되어 있지 않거나, 서로 대각선 방향으로 배치된 경우여야 한다.
• DP[i][0]을 사자가 한 마리도 배치되어 있지 않은 우리를 i - 1행에 추가하는 경우의수, DP[i][1]을 왼쪽 또는 오른쪽에 사자가 한 마리 배치되어 있는 우리를 i - 1행에 추가하는 경우의 수라고 할 때, 위의 두 가지 조건을 식으로 나타내보면 다음과 같다.
  • dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
  • dp[i][1] = dp[i - 1][0] * 2 + dp[i - 1][1]
• 즉, 현재 우리에 비어있는 우리를 추가하는 경우의 수(dp[i][0])는 현재 우리의 마지막 행이 모두 비어있는 경우(dp[i - 1][0]) + 현재 우리의 마지막 행에 사자가 한 마리 배치되어 있는 경우(dp[i - 1][1])인 것이며
• 현재 우리에 사자가 배치되어 있는 우리를 추가하는 경우의 수(dp[i][1])는 현재 우리의 마지막 행이 모두 비어있는 경우(dp[i - 1][0]) + 현재 우리의 마지막 행의 왼쪽 또는 오른쪽에 사자가 배치되어 있는 경우(dp[i - 1][1])인 것이다.
  • 이때 dp[i - 1][0]에 x2 연산을 해준 이유는, 비어있는 우리의 경우에는 추가되는 우리의 왼쪽에 사자가 배치된 경우와 오른쪽에 사자가 배치된 경우를 모두 고려해주어야 하기 때문이다.

 

💻 소스코드

MOD = 9901
n = int(input())
dp = [[0, 0] for _ in range(n + 1)]

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

for i in range(2, n + 1):
    dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
    dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1]) % MOD

print((dp[n][0] + dp[n][1]) % MOD)