[BOJ] 1309 동물원 - JAVA

1. 문제

1309번: 동물원

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

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

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

---

2. 풀이

N=1일 때, 10 / 01 / 00인 경우는 각각 1씩이다.

N=2일 때, 10 / 01 / 00인 경우는 2,2,3이다.

N=3일 때, 10 / 01 / 00인 경우는 5,5,7이다.

N=i일 때, 10인 경우의 개수는 i-1에서 01인 경우 + 00인 경우의 수다.

01인 경우의 개수는 i-1에서 10인 경우 + 00인 경우의 수다.

00인 경우의 개수는 i-1에서 10, 01, 00인 경우의 수를 모두 합친 것과 같다.

따라서 10과 01의 경우의 수는 항상 동일하므로 두칸짜리 dp배열에서 0번째 칸은 01,10 경우의 수, 1번째 칸은 00 경우의 수를 저장했다.

식은 다음과 같다.

dp[i][0] = dp[i-1][0]+dp[i-1][1]

dp[i][1] = dp[i-1][0]*2+dp[i-1][1] 

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
		int div = 9901;

		int[][] dp = new int[N+1][2]; //0번째 칸 : 01,10, 1번째 칸:00
		dp[1][0] = 1;
		dp[1][1] = 1;

		for(int i=2;i<=N;i++){
			dp[i][0] = (dp[i-1][0]+dp[i-1][1])%div;
			dp[i][1] = (dp[i][0]+dp[i-1][0])%div;
		}

		System.out.println((dp[N][0]*2+dp[N][1])%div);
	}

}

---

3. 결과