[backjoon] 9095. 1, 2, 3 더하기

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

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

다이나믹 프로그래밍으로 풀어야 하는 문제입니다. 문제 자체는 쉬워 보이는데 저는 사실 생각하느라 애먹었습니다.

다이나믹 프로그래밍은 아시다시피 top-down 방식과 bottom-up 방식이 있습니다. 저는 bottom-up 방식을 사용하였습니다.

해당 이미지는 점화식을 표현한 것입니다. d[4]를 구하기 위해선 결국 d[1] + d[2] + d[3] 이라는 식이 필요하게 되며 d[5]는 d[2] + d[3] + d[4]의 값이 필요하게 됩니다.

따라서 구하려는 값보다 작은 d[n]의 값을 배열에 채워넣고 구하려는 값의 d[n-1] + d[n-2] + d[n-3]을 구하면 됩니다.

수학적으로 어떤 이유로 이 점화식이 가능한지는 조금 생각해 봐야 할 거 같습니다. 다음은 소스 코드입니다.

백준의 문제는 system.in으로 값을 받아야 하기 때문에 메인 메소드의 소스코드를 첨부합니다

package com.company;

import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt();

        int[] arr = new int[11];

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

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