[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 15990

1,2,3의 합으로 연속하지 않고 주어진 수를 표현하는 방법 출력하기

 

- 입력될 수 있는 모든 경우의 수를 저장하기 위해, 2차원 배열 d[100001][4] 로 메모이제이션을 한다.

- d[i][j]는 합해서 i 가 되는 방법 중, 마지막으로 더해지는 수가 j 이다.

- 즉, 합해서 i 가 되는 방법의 수는 d[i][1]+d[i][2]+d[i][3] 이다.

 

- d[1][1], d[2][2], d[3][3]는 예외로 처리하기 위해 if(i == j)일 때는 1을 저장하도록 처리한다.

- d[i][1]를 구하려면, 마지막에 더해지는 수 1을 제외하고 (i-1)에 대한 방법의 수를 구하면 된다.

 

- 이때, 1과 연속이 되지 않기 위해 (i-1)에 대한 방법은 d[i-1][2], d[i-1][3] 두 가지만 해당되게 한다.

 

import java.util.Scanner;

public class BOJ15990 {
    static final int limit=100000;
    static final long mod=1000000009L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        long d[][]=new long[limit+1][4];

        for(int i=1;i<=limit;i++){
            for(int j=1;j<=3;j++){
                if(i==j){
                    d[i][i]=1;
                    break;
                }
                if(j==1){
                    d[i][j]=(d[i-j][2]+d[i-j][3])%mod;
                }
                else if(j==2){
                    d[i][j]=(d[i-j][1]+d[i-j][3])%mod;
                }
                else if(j==3){
                    d[i][j]=(d[i-j][1]+d[i-j][2])%mod;
                }
            }
        }

        while(t-->0){
            int n=sc.nextInt();
            long answer=(d[n][1]+d[n][2]+d[n][3]);
            System.out.println(answer%mod);
        }
    }
}