백준 9095번 1,2,3 더하기(java) - DP

---

이 문제는 규칙을 찾는게 중요하다.

1 = 1

2 = (1+1) , 2

3 = (1+1+1), (1+2), (2+1), 3

4 = (1+1+1+1) (1+1+2) (1+2+1) (1+3) , (2+1+1) (2+2), (3+1)

이렇게 보면 3의 모든 경우의 앞에 1을 더해주고, 2의 모든 경우에 2를 더해주고, 1의 모든 경우에 3을 더해주면 4의 경우의 수가 나온다. 5도 마찬가지로 해보면 2의 경우에 3을 더하고, 3의 경우에 2를 더하고, 4의 경우에 1을 더해주면 5의 모든 경우의 수가 나온다.

 

즉, n을 1,2,3의 합으로 나타내는 방법의 수는 [n-1], [n-2], [n-3]의 경우의 수를 모두 합친 것이다.

 

import java.util.Scanner;

public class Test {
    static int[] dp = new int[11];
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        int[] n = new int[testCase];
        for(int i = 0; i < testCase; i++) {
            n[i] = scanner.nextInt();
        }
        for (int j = 0; j < n.length; j++) {
            System.out.println(result(n[j]));
        }
    }

    static int result(int n) {
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        if(dp[n] != 0) return dp[n];
        if(n >= 4) {
            dp[n] = result(n - 3) + result(n - 2) + result(n - 1);
        }
        return dp[n];
    }
}