[2294 - JAVA] 동전 2

문제

 

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

 

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

 

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

3 15
1
5
12

 

예제 값을 이용해 점화식을 구해야 한다. 3개의 동전이 15가 되는 경우 동전의 수를 구하는 표를 작성해보자

 

DP   |  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
--------------------------------------------------------
1    |  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
--------------------------------------------------------
5    |  0  1  2  3  4  1  2  3  4  5  2  3  4  5  6  3
--------------------------------------------------------
12   |  0  1  2  3  4  1  2  3  4  5  2  3  1  2  3  3

 

1은 15까지 1씩 동전의 개수가 증가된다.

5는 1 ~ 4까지는 1의 동전이 필요하고 5부터는 5의 동전과 1의 동전을 조합해 값을 구할 수 있다.

12는 1 ~ 4는 1의 동전 5 ~ 11은 5의 동전으로 이뤄진 결과 그대로 12부터 1과 조합해 동전의 개수를 구할 수 있다.

 

결국에는 최소 값을 구해야 하기 때문에 dp[i] = Math.min(dp[i] - dp[i - coin[i]] + 1); 를 이용해 dp index에 해당하는 최소값을 할당한다.

 

정답

 

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

class Main {

    static int n, k;

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

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

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

        Arrays.sort(coins);

        int[] dp = new int[k + 1];
        Arrays.fill(dp, 100001);

        dp[0] = 0;

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

        if (dp[k] == 100001) {
            System.out.println(-1);
        } else {
             System.out.println(dp[k]);   
        }
    }
}