[JAVA/백준9095] 1,2,3 더하기 DP

1. 문제

 

2. 문제 풀이

d[n]을 n일 때 방법의 수라고 하였을 때,
n=1일때부터 n=4일때 까지 각 케이스에 따라 생기는 규칙을 찾으면 d[n]=d[n-3]+d[n-2]+d[n-1]이다.
이 때, n<=2인 경우 예외처리를 하고, d=3인 경우 d[3]=d[2]+d[1]+d[0]이므로 d[0]=1로 가정한다.

3. 소스 코드

import java.util.Scanner;

public class Main {
	public static int[] d;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(); // 테스트케이스
		for (int i = 0; i < t; i++) {
			int n = sc.nextInt();
			d = new int[n + 1];
			System.out.println(solve(n));
		}
	}

	public static int solve(int n) {
		d[0] = 1;
		for (int i = 1; i <= n; i++) {
			if (i <= 2)
				d[i] = i;
			else
				d[i] = d[i - 3] + d[i - 2] + d[i - 1];
		}
		return d[n];
	}
}