[JAVA] 백준 (실버3) 9095번 1, 2, 3 더하기

링크

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

---

문제 설명

(정답률 64.325%)
정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

---

입력 예제

3
4
7
10

---

출력 예제

7
44
274

---

정답 코드

$1 = 1$
$2 = 1 + 1$
$2 = 2$
$3 = 1 + 1 + 1$
$3 = 1 + 2$
$3 = 2 + 1$
$3 = 3$
이고 문제에서 주어진 4의 경우에는
1에 3을 더한 것이고
2의 모든 경우에 2를,
3의 모든 경우에 1을 더한 것이다.
dp[4] = dp[3] + dp[2] + dp[1]가 되고
점화식은 $a_n = a_{n-1} + a_{n-2} + a_{n-3}$이 된다.
$a_{n-1}$은 모든 경우에 1을 더한 것,
$a_{n-2}$은 모든 경우에 2를,
$a_{n-3}$은 모든 경우에 3을 더한 것이다.

import java.io.*;

public class Main {

    static Integer[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            dp = new Integer[11];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;

            System.out.println(recur(n));
        }


    }

    static int recur(int x) {

        if (dp[x] == null) {
            dp[x] = (recur(x - 1) + recur(x - 2) + recur(x - 3));
        }
        return dp[x];
    }
}

---

정리

동적 계획법(DP; Dynamic Programming) 문제이다.
DP문제는 그냥 점화식을 찾기 위한 수학문제같다..
나는 기존에 DP문제에서 활용한 recur메소드를 이용하였는데
애초에 입력값의 최대값이 10밖에 안되기 때문에
미리 메모이제이션 배열을 for문으로 생성한 뒤에 메소드 없이 바로 출력하면 될거 같다.