문제

풀이

1. dp 배열을 먼저 최대 개수인 k+1로 채운다.
2. dp[금액] 현재 금액에 필요한 동전 개수랑 dp[금액-현재 동전 크기]+1 비교
3. dp[n]=MIN(dp[n],dp[n-coin]+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));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        int[] coins=new int[n];
        for(int i=0;i<n;i++){
            coins[i]=Integer.parseInt(br.readLine());
        }

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

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

    }

}

#dp