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

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

---

[접근방법]

기존 [1, 2, 3 더하기] 문제와 동일하다.

n의 범위가 1_000_000 까지 확장된 점이 다르다.

때문에 1,2,3으로 구성한 n의 수식의 수를 저장하는 배열인 dp의 자료형을 long으로 선언해야 한다.

 

---

[JAVA 코드]

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{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        
        long[] dp = new long[1_000_001];
        dp[1] = 1; // 1
        dp[2] = 2; // 1+1, 2
        dp[3] = 4; // 1+1+1, 1+2, 2+1, 3
        
        for(int i=4; i<=1_000_000; i++){
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1_000_000_009;
        }

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }

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