[백준 2294] 동전 2 - JAVA // le_effort

사용 알고리즘 : DP

동전 1번과 비슷한 문제

 

포인트는 DP배열을 최대금액 +1 로 설정해주는 것.

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,k;
    static int coin[];
    static int dp[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        coin = new int[n];
        dp = new int[k+1];
        for(int i=0; i<n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        Arrays.fill(dp, 10001);
        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]==10001) {
            System.out.println(-1);
        }
        else {
            System.out.println(dp[k]);
        }
    }
}