백준 자바 Q1309 동물원

백준 문제풀이 Q1309

다이나믹 알고리즘으로 풀었다.

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

   동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 
   경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지
   않는 경우도 하나의 경우의 수로 친다고 가정한다.
 */
 
//다이나믹 프로그래밍 문제
import java.util.Scanner;
 
public class Q1309 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int d[][] = new int[n+1][3];//케이스를 세가지로 나누었다.    0->사자를 넣지않은 경우  1->사자를 왼쪽에 넣은 경우      2->사자를 오른쪽에 넣은 경우
        
        //우리의 크기가 1일때는, 0번,1번,2번 케이스가 한번씩 나온다.
        d[1][0] =1;
        d[1][1] = 1;
        d[1][2] = 1;
        
        for(int i=2; i<n+1; i++) {
            d[i][0] = (d[i-1][0] + d[i-1][1] + d[i-1][2])%9901;//사자를 넣지 않을 경우 ->전의 우리의 모양이 어느 모양이든 상관없다  
            d[i][1] = (d[i-1][0] + d[i-1][2])%9901;//사자를 왼쪽에 넣은 경우 -> 전의 우리 모양이 사자를 넣지 않은 경우이거나 오른쪽에 넣은경우  
            d[i][2] = (d[i-1][0] + d[i-1][1])%9901;
        }
        System.out.println((d[n][0] + d[n][1] + d[n][2])%9901);
        
        
 
    }
 
}