문제

입력

출력

예제

idea

다이나믹 알고리즘에 대해 공부했기 때문에 다음 문제도 일부러 dp를 골랐다. 해보려고 했으나 점화식을 구하는게 너무 어렵다...
결국 점화식은 검색의 도움을 받았다..
점화식을 구하는 법을 익혀야할 것 같다.

정리

점화식은 f(n) = f(n-1) + f(n-2) + f(n-3)

Code

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int X;
		
		int T=in.nextInt();
		int answer[] = new int[T];
		
		for(int q=0;q<T;q++) {
			X=in.nextInt();
			int f[] = new int[X+1];
			
			for(int i=1;i<=X;i++) {
				if(i==1) f[1]=1;
				if(i==2) f[2]=2;
				if(i==3) f[3]=4;
				if(i>3) {
					f[i]=f[i-1]+f[i-2]+f[i-3];
				}
				answer[q]=f[i];
			}	
		}
		for(int i=0;i<T;i++)
			System.out.println(answer[i]);
	}
}

결과