다이나믹 프로그래밍 - 효율적인화폐구성

문제

---

 

 

해설

---

 

 

문제해결

---

1. 각 화폐 단위를 배열로 받는다 (int[] money)

2. 0~m원까지 가지고 있는 화폐로 만들 수 있는 최소 개수를 구하기 위한 dp 배열을 만든다

3. dp 배열의 0원은 0원으로 만들수있으므로(?) 0으로, 나머지는 10001(나올수 없는 최대값)로 초기화 한다

4. 2중 반복문을 돌며 각 화폐마다(mon) i-mon을 만들 수 있으면(dp[i-mon]!=10001) dp[i]와 dp[i-mon]+1의 최소값을 dp[i]에 넣는다

5. 마지막 dp[m]이 10001일 경우 구할 수 없는 경우므로 -1을 그 외는 dp[m]을 출력하면 된다

import java.util.Scanner;

public class Ex04_효율적인화폐구성 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //각 화폐 단위 담는 배열
        int[] money = new int[n];
        for (int i = 0; i < n; i++) {
            money[i] = sc.nextInt();
        }
        //0원은 0으로, 나머지 아직 못구한 값은 10001로 초기화
        int[] dp = new int[m+1];
        for (int i = 1; i <= m; i++) {
            dp[i] = 10001;
        }
        //2중 반복문을 돌며 각 화폐로 구할수 있는 최소 개수를 구한다
        for (int mon : money){
            for (int i = mon; i <= m; i++) {
                if (dp[i-mon] != 10001){
                    dp[i] = Math.min(dp[i], dp[i-mon]+1);
                }
            }
        }
        if (dp[m] == 10001)
            System.out.println(-1);
        else
            System.out.println(dp[m]);

    }
}