[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설

 이번에 풀어볼 문제는 DP문제인 동물원입니다.

1309번: 동물원

이문제는 오르막수와 비슷한 문제 양상을 띄고 있어서, 비슷한 문제 풀이를 이용했습니다.

이차원배열을 통해서 총 3가지의 경우를 나타냈는데 각각의 의미는 이렇습니다

Dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우
Dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우
Dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우

즉, 이전 방의 경우의 수를 계속 취합해서 더할 수 있는습니다.
문제는 주어져있는 조건 "사자를 넣은 방에는 오른쪽방과 아랫방에는 넣을 수 없다" 라는 조건때문에, 사자를 넣지 않은 경우를 빼고는 지금 n번방에 넣은 곳 위치에 따라서 넣어야할 사자의 위치가 정해집니다.

dp[i][0] = dp[i-1][0] + dp[i-1][1] +dp[i-1][2]; -> 이번 방에서는 넣지 않을 것이므로, 이전방에서 사자가 어디 방에 들어있든 상관 없음

dp[i][1] = dp[i-1][0] + dp[i-1][2]; -> 이번방에는 왼쪽에 넣을거니까 이전방에는 오른쪽 혹은 없는 경우만 됨.

dp[i][2] = dp[i-1][0] + dp[i-1][1]; -> 이번방에는 오른쪽에 넣을거니까 이전방에는 왼쪽 혹은 없는 경우만 됨. 

 

 

/** 2020. 4. 30. 오후 11:47:12
 * @author ventulus95
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int dp[][];

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1][3];
		Arrays.fill(dp[1], 1);
		for(int i=2; i<=n; i++){
			dp[i][0] = dp[i-1][0] + dp[i-1][1] +dp[i-1][2]; 
			dp[i][1] = dp[i-1][0] + dp[i-1][2];
			dp[i][2] = dp[i-1][0] + dp[i-1][1];
			dp[i][0] %= 9901;
			dp[i][1] %= 9901;
			dp[i][2] %= 9901;
		}
		int sum = 0;
		for(int i =0; i<3; i++){
			sum+=dp[n][i];
		}
		System.out.println(sum%9901);
	}
}