[DP]문제#1. 1,2,3 만들기(백준 9095번),자바

 

9095번: 1, 2, 3 더하기 (acmicpc.net)

*참고해서 푼 문제

이 문제는 d[i]=d[i-3]+d[i-2]+d[i-1]; 라는 규칙이 있었다.

1,2,3으로 만들수 있는 조합의 개수는 구했는데, 그 조합의 순열까지 고려해야하는 부분에 대해서는 미처 생각해내지 못했다.

import java.util.Scanner;

public class Main {

	static int T;
	static int n;
	static int[] dp;
	public static void main(String[] args) {

		Scanner in=new Scanner(System.in);
		T=in.nextInt();
		
		while(T>0) {
			n=in.nextInt();
			dp=new int[n+1];
			dp[0]=1;
			dp[1]=1;
			if(n>=2) {
				dp[2]=dp[0]+dp[1];
				for(int i=3;i<=n;i++) {
					dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
				}
			}
			System.out.println(dp[n]);
			T--;
		}
	}
}