[백준] 9095번 : 1, 2, 3 더하기(JAVA)

점화식이 나온 근거를 찾자!

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

위의 문제는 BaekJoon Online Judge의 알고리즘 분류 중

 

다이나믹 프로그래밍의 카테고리에 포함되어 있는 문제이다.

 

Dynamic Programming에 슬슬 재미가 붙고 있는 참이다.

 

정수 1을 1, 2, 3의 합으로 나타내는 방법은 1로 총 1가지이며,

 

2는 1+1, 2로 2가지, 3은 1+1+1, 1+2, 2+1, 3 4가지이다.

 

4는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 총 7가지이다.

 

점화식을 구하면 n > 3일 때, f(n) = f(n-1) + f(n-2) + f(n-3)이라는 식이 나오게 되는데.

 

f(4)를 예로 들면, f(n-1)인 f(3)의 방법들에 +1을 하면 4가 된다.

 

마찬가지로 f(2)의 방법들에 +2를 하면 4가 되고,

 

나머지 f(1)의 방법들에 +3을 하면 4가 된다.

 

중복은 발생되지 않는다.

 

import java.util.Scanner;

public class Question_9095 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int Test_Case = sc.nextInt();
		
		int[] Sequence = new int[11];
		
		Sequence[0] = 1;
		Sequence[1] = 1;
		Sequence[2] = 2;
		
		for(int i = 3; i < Sequence.length; i++) {
			Sequence[i] = Sequence[i-1] + Sequence[i-2] + Sequence[i-3];
		}
		
		for(int i = 0; i < Test_Case; i++) {
			int N = sc.nextInt();
			System.out.println(Sequence[N]);
		}
	}
}