백준 1309번 동물원 [DP] :: 마이구미

이번 글은 백준 알고리즘 문제 1309번 "동물원"을 다뤄본다.

이 문제의 접근법은 동적계획법 즉, DP이다.

 

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

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

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

 

문제의 포인트는 가로, 세로로 붙어서 배치할 수 없고, 배열은 2 * N 배열이다.

배치할 수 있는 경우는 가로나 세로가 붙어있지만 않으면 된다.

 

 

문제 해결법은 DP이지만, 기본적인 DP 접근 방식이 아닌 조금 다른 접근이 필요하다.

먼저 사자를 배치할 수 있는 경우를 보자.

 

사자를 배치할 수는 경우는 3가지가 존재한다.

1. N번째 줄에 사자가 모두 없을 경우

2. N번째 줄에 왼쪽 칸에만 사자가 있는 경우

3. N번째 줄에 오른쪽 칸에만 사자가 있는 경우

 

1번의 경우.

현재 줄에 사자가 모두 없다면 윗줄에는 사자가 왼쪽 칸 배치 가능.

윗줄 오른쪽 칸 배치 가능.

윗줄 모두 미배치 가능.

 

2번의 경우

현재 줄 왼쪽 칸에 사자가 있음으로 윗줄 오른쪽 칸에 사자 배치 가능.

윗줄 모두 미배치 가능.

 

3번의 경우

현재 줄 오른쪽 칸에 사자가 있음으로 윗줄 왼쪽 칸에 사자 배치 가능.

윗줄 모두 미배치 가능.

 

위를 토대로 점화식을 도출할 수 있다.

 

// 사자가 왼쪽 오른쪽 둘다 들어가 있지 않을 경우 => 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];

 

점화식을 가지고 코드로 구현해보면 아래와 같다.

 

for (int i = 2; i <= n; i++) { 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; }

 

사실 이 문제를 풀 때 규칙을 찾아 쉽게 dp로 풀 생각을 했을거라 생각한다.

규칙 찾기가 까다롭지만 규칙은 존재한다.

 

n = 1 => 1

n = 2 => 3

n = 3 => 17

n = 4 => 41

 

dp[n] = dp[n-1]*2 + dp[n-2]

 

2가지 방법으로 풀 수 있다.

전자로 접근해보길 바란다.

전체 소스는 아래 Github URL을 참고하길 바란다.

 

백준 1309번 동물원 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/1309.java