9095

해결해야하는 문제

1. 수를 1,2,3의 값의 합으로 나누고 경우를 어떻게 따질지

해결방법

1. (내 방법) 펙토리얼을 이용하여 해결하려했다
2. dp방법으로 해결 점화식을 통해

풀이

bottom-up방식

d[0] = 0
d[1] = 1
d[2] = 1+1, 2
d[3] = 1+1+1, 1+2, 2+1, 3
d[4] = 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1

import java.util.Scanner;

public class plus9095 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        int[] array = new int[11];

        array[0] = 0;
        array[1] = 1;
        array[2] = 2;
        array[3] = 4;

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

    }
}