백준 1309번 동물원 [JAVA]

문제

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

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

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

입력

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

출력

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

 

 

 

이 문제는 처음에 접근을 잘못했다 하지만 문제가 풀렸을때는 엄청난 희열을 느낀 문제였다

우리의 한줄에는 2칸이 있는데 그 2칸중 한 칸에 사자가 무조건 존재해야 된다고 가정하고 풀었는데

생각해보니 우리의 한줄에 사자가 없는경우도 경우의수 중 하나였다 

 

알고리즘 설계 

dp[n][0]-> 2xn인 배열의 마지막줄에 사자를 안가두는 경우 
dp[n][1]-> 2xn인 배열의 마지막줄의 왼쪽에 사자를 가두는 경우 나올수 있는 경우의수
dp[n][2]-> 2xn인 배열의 마지막줄의 오른쪽에 사자를 가두는 경우 나올수 있는 경우의수


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]
->이번방에는 오른쪽에 넣을거니까 이전방에는 왼쪽 혹은 없는 경우만 됨.

dp[n][0]+dp[n][1]+dp[n][2]=> 2xn 배열에 사자를 가둘 수 있는 모든 경우의 수

ex)
dp[1][0]=1;
dp[1][1]=1;
dp[1][2]=1;

dp[2][0]=dp[1][0]+dp[1][1]+dp[1][2]=3 
dp[2][1]=dp[1][0]+dp[1][2]=2
dp[2][2]=dp[1][0]+dp[1][1]=2

dp[2][0]+dp[2][1]+dp[2][2]=7     >2x2배열에 사자를 가둘 수 있는 모든 경우의 수

 

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long [][]dp=new long[n+1][3];

        dp[1][0]=1;
        dp[1][1]=1;
        dp[1][2]=1;

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

        long answer=(dp[n][0]+dp[n][1]+dp[n][2])%9901;

        System.out.print(answer);
    }
}

 

 

역시 dp문제는 현재상태의 여러가지 case와 그에 따라 올수 있는 직전상태를 case로 나눠서 풀면 잘풀린다

 

현재상태

case 1. 이번방에 사자를 가둔경우

case 2. 이번방에 사자를 왼쪽에 가둔경우

case 3. 이번방에 사자를 오른쪽에 가둔경우

 

 

case1에 따른 직전상태의 case: 이번 방에서는 넣지 않을 것이므로, 이전방에서 사자가 어디 방에 들어있든 상관 없음 

case2에 따른 직전상태의 case: 이번방에는 왼쪽에 넣을거니까 이전방에는 오른쪽 혹은 없는 경우만 됨.

case3에 따른 직전상태의 case: 이번방에는 오른쪽에 넣을거니까 이전방에는 왼쪽 혹은 없는 경우만 됨.