[백준][9095번] 1,2,3 더하기

문제 URL

https://www.acmicpc.net/submit/9095/21392705

나의 풀이

import java.io.*;

public class Main {
    public static final int MAX = 10;
    public static int[] d = new int[MAX + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int size = Integer.parseInt(br.readLine());
        dp(MAX);

        while (size-- > 0) {
            int num = Integer.parseInt(br.readLine());
            bw.write(d[num] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static int dp(int n) {
        //수를 0개씩 사용한것도 1
        if (n == 0)
            return 1;
        else if (n < 0)
            return 0;
        if (d[n] > 0)
            return d[n];

        for (int i = 1; i <= 3; i++)
            d[n] += dp(n - i);
        return d[n];
    }
}

느낀점

동적계획법 을 이용한 문제다.

D[i] = i를 1,2,3의 합으로 나타내는 방법의 수 D[i] = D[i-1] + D[i-2] + D[i-3] 이다. 또한, D[0] = 1 이다. 1,2,3을 각각 0번 사용한것도 방법의수 1이기 떄문이다.