[백준] 9095번 - 1, 2, 3 더하기

 

1, 2, 3에 해당하는 조합의 개수는 1, 2, 4이고 4부턴 이 3개의 값을 이용하는 다이나믹 프로그래밍 문제이다.

4와 같은 경우 1에서 3을 더해주고, 2에서 2를, 3에서 1을 더해주기 때문에 cnt(4) = cnt(1) + cnt(2) + cnt(3)으로 표현할 수 있다. 이를 일반화하게 되면

​

라고 표현을 할 수 있다. 이를 코드로 작성하면 아래와 같다.

import java.util.Scanner;

public class p9095 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] ary = new int[11];

		ary[1] = 1;
		ary[2] = 2;
		ary[3] = 4;

		for (int i = 4; i < ary.length; i++) {
			ary[i] = ary[i - 1] + ary[i - 2] + ary[i - 3];
		}
		for (int i = 0; i < a; i++) {
			int n = sc.nextInt();
			System.out.println(ary[n]);
		}
	}
}