[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 9095

1,2,3의 합으로 주어진 수를 표현하는 방법 출력하기

 

주어진 수가 1,2,3일 때, 각각의 반환값 1,2,4를 저장한다.

 

덧셈으로 표현될 때

마지막 더해지는 수가 1,2,3인 경우를 생각하여

d[x]=d[x-1]+d[x-2]+d[x-3] 을 작성한다.

 

import java.util.Scanner;

public class BOJ9095 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] d = new int[n + 1];
            System.out.println(operate(n, d));
        }
    }

    static int operate(int x, int[] d) {
        if (x == 1) return 1;
        if (x == 2) return 2;
        if (x == 3) return 4;
        if (d[x] > 0) return d[x];

        for (int i = 1; i <= 3; i++) {
            d[x]+=operate(x-i,d);
        }
        return d[x];
    }
}