[Algorithm] 효율적인 화폐 구성

문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.

이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

 

입력 조건

첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)

이후 N개의 줄에는 각 화폐의 가치가 주어진다.

 

출력 조건

첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.

불가능할 경우 -1을 출력한다.

 

풀이

M원에 도달하기까지 최소한의 화폐를 사용하는 것이 필요하다.

만약, 2개의 화폐 1원, 3원이 주어진다고 가정하자.

그렇다면 M-1원까지의 갯수 + 1과 M-3원까지의 갯수 + 1 중 작은 값이 M원에 도달하기까지 최소한의 화폐를 사용한다고 할 수 있다.

 

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    int[] d = new int[10001];
    int n, m;

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();

    int[] value = new int[n];
    for(int i = 0; i < n; i++) {
      value[i] = sc.nextInt();
    }
    sc.close();

    for (int i = 1; i < d.length; i++) {
      d[i] = 10001; // 배열 초기화, 큰 값
    }

    d[0] = 0; // 0일 땐, 0
    for (int v : value) { // 화폐 단위별로 
      for (int i = v; i <= m; i++) { // M원까지 모든 값에 대해서
        if (d[i - v] != 10001) { // i-v원이 계산이 가능하다면
          d[i] = Math.min(d[i], d[i-v]+1); // 지금 값과 뺀 값의 최소값을 대입
        }
      }
    }

    if (d[m] == 10001) {
      System.out.println(-1);
    } else {
      System.out.println(d[m]);
    }
    


  } // end main
}