[BOJ] 백준 1309번 : 동물원 (JAVA)

문제

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

 

 

 

 

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

 

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

 

 

입력

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

 

 

출력

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

 

 

풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

동물을 특정 공간에 설치하되, 각 동물이 상하좌우로 겹치면 안 되도록 설치하는 것이 핵심이었습니다.

 

저는 이 문제를 풀기 위해서

dp[i][j] = n : i번째 줄에서, j번째 칸에 동물을 놓을 수 있는 경우의 수는 n

과 같이 dp 배열을 정의하였습니다.

 

여기서 j번째가 나타내는 것이 중요했는데, j가 0일 때는 아무 곳에도 동물을 놓지 않는 경우이고, j가 1일 때는 첫 번째 칸, j가 2일 때는 두 번째 칸에 동물을 놓는다는 뜻이었습니다.

 

N = 1일 때는 기저 사례로 가정하여, dp[1][0] = dp[1][1] = dp[1][2] = 1로 설정합니다.

그리고 N = 2일 때는 어떻게 점화식을 세울 수 있는지 봅시다.

 

(1) 두 번째 줄에 동물을 놓지 않는 경우

dp[2][0] 이 몇 인지 판단하는 케이스입니다.

그리고 이것은 dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2] = 3 과 같습니다.

두 번째 줄에 아무 동물도 놓지 않으면, 첫 번째 줄에는 어떠한 영향도 받지 않기때문이죠.

 

(2) 두 번째 줄의 첫 번째 칸에 동물을 놓는 경우

dp[2][1] 이 몇 인지 판단하는 케이스입니다.

두 번째 줄의 첫 번째 칸에 동물을 놓게 되면, (1, 1) 과 (2, 2) 에는 동물을 놓을 수 없게 됩니다.

따라서 dp[2][1] = dp[1][0] + dp[1][2] = 2 와 같습니다.

 

(3) 두 번째 줄의 두 번째 칸에 동물을 놓는 경우

dp[2][2] 이 몇 인지 판단하는 케이스입니다.

두 번째 줄의 두 번째 칸에 동물을 놓게 되면, (1, 2) 와 (2, 1) 에는 동물을 놓을 수 없게 됩니다.

따라서 dp[2][2] = dp[1][0] + dp[1][1] = 2 와 같습니다.

 

(1) ~ (3) 에 따라, 2 x 2 공간에서 동물을 놓을 수 있는 경우의 수는 7 이 됩니다.

그리고 이를 일반화하여 점화식을 아래와 같이 표현할 수 있습니다.

 

 

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]

 

 

위 식을 이용하여 중간에 적절히 MOD를 나눠주면 정답을 구해낼 수 있습니다.

아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.