백준 2294번 동전 2(JAVA)

문제

2294번: 동전 2

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        int[] dp = new int[k + 1];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(dp, 100001); // 동전의 최대 가치가 100000이므로 1원짜리를 100000개 이용하는 최악의 경우로 초기화한다.
        dp[0] = 0; // 0개의 동전으로 만들 수 있는 돈은 없다.

        for (int i = 0; i < n; i++) {
            for (int j = arr[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
            }
        }

        System.out.println(dp[k] == 100001 ? -1 : dp[k]);
    }
}

초기 상태(dp[1]부터)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

i = 1)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

i = 5)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	1	2	3	4	5	2	3	4	5	6	3​

i = 12)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	1	2	3	4	5	2	3	1	2	3	3​​​​