[9095번] 1,2,3 더하기

✅ 점화식

1,2,3 으로 구성되어 있으므로 이전 3번째 항까지만 중복검사를 해주면 된다.

점화식

dp[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 

✅ 코드

import java.util.Scanner;

public class Main {
	static int[] dp;

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

		for (int t = 0; t < test; t++) {

			int n = sc.nextInt();

			dp = new int[n + 1];

			dp[0] = 1;
			dp[1] = 1;

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

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

		}

	}
}