[백준] 15988번 : 1, 2, 3 더하기 3 - JAVA [자바]

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

n = 1
1

n = 2
1+1
2

n = 3
1+1+1
1+2
2+1
3

n = 4
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

자세히 보면
n 을 1, 2, 3의 합으로 나타내는 방법은

1. n-1을 1, 2, 3의 합으로 나타내는 방법 뒤에 +1을 한 방법들과
2. n-2을 1, 2, 3의 합으로 나타내는 방법 뒤에 +2을 한 방법들과
3. n-3을 1, 2, 3의 합으로 나타내는 방법 뒤에 +3을 한 방법으로 이루어져 있다.
   

즉, 방법의 수 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

MOD 나누기 까먹지 말자!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class bj15988 {

    private static final int MOD = 1_000_000_009;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 범위를 유의해서 long으로 정의한다.
        long[] dp = new long[1000001];

		// 1부터 3까지는 구했으니까 초기화
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        // 4부터 n이 나올 수 있는 범위까지 미리 구한다.
        for (int i = 4; i < 1000001; i++) {
        	// 점화식 적용
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
        }
        // Test Caset 수를 입력 받고
        int T = Integer.parseInt(br.readLine());
        // 반복문을 돌며
        for (int i = 0; i < T; i++) {
        	// 수를 입력받고
            int num = Integer.parseInt(br.readLine());
            // 값을 출력한다
            bw.write((dp[num]) % MOD + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}