[백준] 9905 1, 2, 3 더하기 (JAVA)

 

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

9095번: 1, 2, 3 더하기

풀이

위의 문제는 기본적인 dp문제이다. 우선 접근법은 간단하다. 우리는 어떠한 수 x가 들어온다고 하였을경우 x-1, x-2, x-3을 한다. 그 이후 각각의 수가 만약 이전에 계산하여 구했던 적이 있다면 그대로 dp배열에 있는 값을 반환해준다. 예를 들어 4를 x라고 하였을 경우 우리는 3 + 1, 2 + 2, 1 +3을 하여 경우의 수를 구하게 된다. 이때 각각의 연산값을 자세히 보면 3 + 1의 경우는 1, 2, 3만으로 3을 만들었는 경우에서 1을 각각 더하면 4가 되기에 우리는 dp[3]이 3 + 1 이라는 연산의 결과값임을 알수있게 된다. 이의 연장선상으로 2 + 2를 한다면 1, 2 ,3을 통해 2를만드는 경우에 각각 2를 더하면 되기에 이는 즉 dp[2] + 2가 된다. 이렇게 하여 변수 x가 들어올경우 x-1, x-2, x-3의 경우를 차례차례 더하면 된다. 자세한것은 코드를 보면 이해가 될것이다.

 

코드

import java.io.*;

class Main {
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int t;
        dp = new int[12];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            t = Integer.parseInt(br.readLine());
            bw.write(calc(t) + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static int calc(int x) {
        if (dp[x] != 0) {
            return dp[x];
        } else {
            for (int i = 1; i <= 3; i++) {
                if (x - i >= 0) {
                    dp[x] = dp[x] + calc(x - i);
                }
            }
            return dp[x];
        }
    }
}