[BOJ] 1309번 동물원

[BOJ] 1309번 동물원 문제

꽤 어려웠던 DP(Dynamic Programming) 문제다.

이 문제는 DP 중에서도 2차원 배열을 이용하는 DP 문제다. 1차원 배열 DP 풀이도 있으나 이해하기엔 너무 어렵기에 여기서는 2차원 배열을 이용한다.

---

핵심은 N번째 층에서 사자가 없을 때 / 왼쪽에 있을 때 / 오른쪽에 있을 때로 나누고, N번째 층의 위쪽(즉, N-1번째) 층에 따라 해당 층에는 어떨 때에 사자를 배치할 수 있는지 없는지를 확인하는 것이다. 또한 사자를 안 두는 방법도 하나의 방법이라는 것도 인지해야 한다.

이를 위해 각 층마다 [사자가 없을 때, 왼쪽에 있을 때, 오른쪽에 있을 때]라는 배열로 둘 수 있다.

먼저 1개의 층만 있을 때를 보자. 간단하게 안 두기, 왼쪽에 두기와 오른쪽의 두기로 총 3개의 경우가 나온다. 초깃값은 기본적으로 우리가 직접 구해줘야 한다.

2×1의 우리가 있을 때의 모든 경우의 수

그렇다면 2개의 층이 있을 때를 보자. 사자는 인접한 가로와 세로에 같이 둘 수 없다는 문제의 규칙에 의거하면 아래와 같은 경우가 나온다.

• 2층에 사자를 안 둔다면 1층에 배치 가능한 경우의 수는 안 두기, 왼쪽에 두기와 오른쪽에 두기로 총 세 가지다.
• 2층에 사자를 왼쪽에 둔다면 1층에 배치 가능한 경우의 수는 안 두기와 오른쪽에 두기로 총 두 가지다.
• 2층에 사자를 왼쪽에 둔다면 1층에 배치 가능한 경우의 수는 안 두기와 왼쪽에 두기로 총 두 가지다.

이를 그림으로 보면 아래와 같이 총 7가지가 나온다. 이 그림에서 2층은 밑쪽에 있다.

2×2의 우리가 있을 때의 모든 경우의 수

3층이어도 똑같다. 위의 규칙대로 구하면 아래와 같이 17가지가 나온다.

2×3의 우리가 있을 때의 모든 경우의 수

N개의 층이라 해도 위의 규칙대로 구하면 된다.

---

이제 위에 있는 말들을 점화식으로 나타내어보자. 배열의 이름은 $ DP $로 둔다.

먼저 배열은 $ N \times 3 $의 꼴이 된다. $ DP[N][0] $은 $ N $층에 사자를 배치하지 않는 경우의 수고, $ DP[N][1] $은 $ N $층에 사자가 왼쪽에 있을 때의 경우의 수고, $ DP[N][2] $는 $ N $층에 사자가 오른쪽에 있을 때 배치할 수 있는 경우의 수다.

$ DP[N][0] $은 전 층인 $ N-1 $에서 사자를 배치하지 않을 때의 경우, 왼쪽에 배치했을 때의 경우, 그리고 오른쪽에 배치했을 때의 경우를 전부 합해주면 된다. 즉, $ DP[N][0] = DP[N-1][0] + DP[N-1][1] + DP[N-1][2] $이다.

$ DP[N][1] $은 전 층인 $ N-1 $에서 사자를 배치하지 않을 때의 경우와 오른쪽에 배치했을 때의 경우를 합해주면 된다. 즉, $ DP[N][1] =DP[N-1][0] +DP[N-1][2] $이다.

$ DP[N][2] $은 전 층인 $ N-1 $에서 사자를 배치하지 않을 때의 경우와 왼쪽에 배치했을 때의 경우를 합해주면 된다. 즉, $ DP[N][2] =DP[N-1][0] +DP[N-1][1]$이다.

즉, 다시 옮겨 적으면 이 2차원 배열의 점화식은 아래와 같이 나타내어진다.

$ DP[N][0] = DP[N-1][0] + DP[N-1][1] + DP[N-1][2] $
$ DP[N][1] = DP[N-1][0] + DP[N-1][2] $
$ DP[N][2] = DP[N-1][0] + DP[N-1][1] $

 

여기서 $ N $층에서의 모든 경우의 수를 구하고 싶다면 $ DP[N] $의 모든 요소를 더하면 된다.

---

이 점화식을 코드로 나타내어보자. 특히 이 문제에서는 9901로 나눈 나머지를 출력해야 하니 잊지 말자.

import sys

if __name__ == '__main__':
	N = int(sys.stdin.readline().rstrip())
	dp, modi = [[0, 0, 0], [1, 1, 1]], 9901
	for i in range(2, N+1):
		dp.append([(dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%modi, (dp[i-1][0] + dp[i-1][2])%modi, (dp[i-1][0] + dp[i-1][1])%modi])
		
	print(sum(dp[N])%modi)

 

위의 말을 그대로 코드로 옮겼다. dp 배열은 N을 그대로 써먹기 위해 0번째 원소를 임의로 넣었다.

for문은 N이 1이어도 돌지 않고 2 이상일 때에만 돌게 되어있다. 그리고 각 원소마다 9901을 넣은 변수인 modi로 나머지 연산을 시켜준다. 아무리 파이썬이라 해도 $ N = 100,000 $이라는 제한도 있고, 숫자도 선형적으로 커지는 만큼 메모리를 엄청 잡아먹기 때문에 나머지 연산을 하는 게 낫다.

마지막에 dp[N]의 모든 요소를 더한 후 마지막으로 한번 더 9901의 나머지 연산을 시킨 값을 출력하는 것을 잊지 말자.