[Java] 15988번: 1, 2, 3 더하기 3 Silver 2

문제 링크

이 문제는 밥 먹으면서 문제 보다가 풀었다.. ㅋㅋ

보면, 4을 만드는 방법은 7가지인데,

1, 2, 3을 만드는 방법에서 각각 뒤에
3, 2, 1을 붙이면 4를 만드는 모든 케이스를 만들 수 있다!

DP에서는 N을 만드는 방법만 알면 된다고 했으니, 이 문제는 다 푼 것이다!

점화식은 그래서
X[N] = X[N-1] + X[N-2] + X[N-3]이다.

정답

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // T 입력 받기
        int T = Integer.parseInt(br.readLine());

        // dp
        long[] dp = new long[1000000];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        for (int i = 3; i < 1000000; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
        }

        // 출력
        for (int i = 0; i < T; i++) {
            int input = Integer.parseInt(br.readLine());
            System.out.println(dp[input - 1]);
        }
    }
}