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

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

1, 2, 3 더하기랑 똑같은 방법으로

N번째 항은 [N-1까지의 합 + 1] + [N-2까지의 합 + 2] + [N-3까지의 합 + 3]

과 같으므로 아래와 같이 작성하였습니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        long[] num = new long[1000001];
        long mod = 1000000009L;

        num[1] = 1;
        num[2] = 2;
        num[3] = 4;
        for (int i = 4; i <= 1000000; i++)
            num[i] = (num[i - 1] + num[i - 2] + num[i - 3]) % mod;
        while (T-- > 0)
            sb.append(num[Integer.parseInt(br.readLine())] + "\n");
        System.out.print(sb);
    }
}