동전 2 2294

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

DP는 어렵다..

각 동전의 가치를 coin이라고 할 때, 금액 i를 만드는 데 필요한 최소 동전의 개수는 다음 두 가지 방법 중 하나로 만들 수 있다

이전에 계산한 dp[i]의 값 (현재 동전을 사용하지 않는 경우)
dp[i - coin] + 1의 값 (현재 동전을 사용하는 경우)
이 둘중에 작은것을 선택하여 dp[i]에 갱신한다

점화식
dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);
j = 현재목표금액(최소의 동전을 사용해서)

'coin[i]' 를 사용하는 경우
j(현재만들고자하는금액) - coni[i](동전을 사용하므로 뺀다)
= 이전에 구했던 만들고자 하는 금액에 최소 필요한 동전개수 + 1(새로운 동전을 사용했으므로)

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));

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);

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

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

        Arrays.sort(coin);
        Collections.reverse(Arrays.asList(coin));

        for (int i = 0; i < k+1; i++) {
            dp[i] = k+1;
        }
        dp[0] = 0;

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

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