[BOJ 2294] 동전2

[BOJ 2294] 동전2

 

1. 문제 : Link

동전1과 비슷하지만 최솟값을 구하는 문제

 

2. 풀이

dp[0]  = 0

각 dp 값은 해당 값에서 - 코인 한 값 + 1 (개수가 하나 늘어나는것)

기존 dp 값과 비교해서 min값 넣어주기

 

10001 (최댓값)이라면 -1 출력

 

3. 코드

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

public class Main {
    static int N;
    static int sum;
    static int[] coins;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        sum = sc.nextInt();

        coins = new int[N];

        for(int i=0; i<N; i++){
            coins[i] = sc.nextInt();
        }

        dp = new int[sum+1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;

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

        if(dp[sum] == 10001) System.out.println(-1);
        else System.out.println(dp[sum]);

    }
}