[백준] 15988번 1,2,3 더하기 3

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

정수 N	경우의 수	개수
1	1	1
2	1+1 2	2
3	1+1+1 1+2 2+1 3	4
4	1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1	7	4 + 2 + 1 dp[3] + dp[2] + dp[1]
5	1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 1+1+3 1+3+1 3+1+1 1+2+2 2+1+2 2+2+1 2+3 3+2	13	7 + 4 + 2  dp[4] + dp[3] + dp[2]

 

점화식 : dp[N] = dp[N-1] + dp[N-2] + dp[N-3]

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        int N = Integer.parseInt(br.readLine());
        long mod = 1000000009;
        long[] dp = new long[1000000 + 1];
        dp[1] = 1 % mod;
        dp[2] = 2 % mod;
        dp[3] = 4 % mod;
        for(int j = 4; j <= 1000000; j++) {
        	dp[j] = (dp[j-1]+dp[j-2]+dp[j-3]) % mod;
        }

        for(int i = 0;  i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            sb.append(dp[num]).append("\n");
        }

        System.out.println(sb);
    }
}