[BOJ] 15988번 1, 2, 3 더하기 3 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.Scanner;

public class Main {
	static int n, t;
	static long[] dp = new long[1000001];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

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

		t = sc.nextInt();
		for (int tc = 0; tc < t; tc++) {
			n = sc.nextInt();

			if (n > 3) {
				for (int i = 4; i <= n; i++) {
					dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
				}
			}

			System.out.println(dp[n]);
		}
	}
}

📄 해설

• n = 5, 6 까지 경우를 구해보면 아래와 같은 점화식이 얻어짐
  dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]