[백준] 동전2

참고 : www.acmicpc.net/problem/2294

 

 

- dp 문제

- dp[i] : i 에 도달하는데 최소 갯수

(ex. dp[1] : 1에 도달하는데 최소 갯수 1이 있을 시 1로 최소)

 

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final int MAX_VAL = 100001;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] coin = new int[n+1];
        for(int i=1; i<=n; i++) {
            coin[i] = sc.nextInt();
        }
        int[] dp = new int[10002];
        dp[0] = 0;
        for(int i=1;i<=k;i++) {
            dp[i] = MAX_VAL;
        }
        for(int i=1;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] == MAX_VAL) {
            System.out.println(-1);
            return;
        }
        System.out.println(dp[k]);
    }
}