백준 15988번 자바 : 1,2,3 더하기 3

다이나믹 프로그래밍 - int 오버플로우에 유의

(int + int + int) %100
앞의 합산 과정에서 int 오버플로우가 발생할 수 있으므로 결과는 예상치 못한 음수값이나 잘못된 양수값이 나올 수 있다. 따라서 나머지 연산을 수행하더라도 잘못된 결과가 나올 수 있음.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int T, n;
    static long[] dp = new long [1000001];
    static StringBuilder sb = new StringBuilder();
    static int div = 1000000009;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<dp.length; i++) {
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%div;
        }

        while(T-->0) {
            n = sc.nextInt();
            sb.append(dp[n]);
            sb.append('\n');
        }

        System.out.println(sb.toString());
    }

}