DP - 효율적인 화폐 구성

문제

이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/5Lu34WIx2Us)

• 화폐의 종류는 N가지.
• 각 종류 화폐의 사용 개수는 제한이 없다.
• M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하라.

 

입력 조건

• 첫째 줄에 화폐 개수 N, 만들려는 금액 M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에 각 화폐의 액수를 기재 (<= 10,000)

 

출력 조건

• 첫째 줄에 최소 화폐 개수를 출력
• 불가능할 때는 -1을 출력

 

풀이

• f(i) = 금액 i를 만들 수 있는 최소한의 화폐 개수
• k = 각 화폐의 단위
• 각 화폐 단위인 k를 하나씩 확인하며 f(i-k)를 만드는 방법이 존재하는지 체크한다.
  존재할 경우 해당 화폐 개수에 k화폐를 하나 추가하면 f(i) 값이 구해진다.

 

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

// 효율적인 화폐 구성
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // N개의 화폐 단위 정보 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // DP 테이블 초기화 (일단 모두 불가능한 것으로)
        int[] d = new int[m + 1];
        Arrays.fill(d, 1001);

        // 다이나믹 프로그래밍 Bottom-Up (각 화폐단위 별로 모든 금액 계산)
        for (int i = 0; i < n; i++) {
            for (int j = arr[i]; j <= m; j++) {
                // (j - 화폐단위)원을 만드는 방법이 존재하는 경우
                if (d[j - arr[i]] != 1001) {
                    d[j] = Math.min(d[j], d[j - arr[i]] + 1);   // 기존 값과 방금 계산한 값 중 최소값
                }
            }
        }
        
        // 불가능한 경우만 -1 출력
        if(d[m] == 1001) System.out.println(-1);
        else System.out.println(d[m]);
    }
}