효율적인 화폐 구성

 

이 문제도 전형적으로 보텀업 방식을 이용해서 풀리는 문제이다.

m원에 대한 최소 화폐 개수를 저장해놓는 d[m] 배열을 설정해놓고 화폐 단위에 따라 m원까지 탐색해나간다.

 

3원부터 시작해서 m원 까지 만들 수 있는 화폐 갯수

5원부터 ~ 

7원부터 ~

각 탐색시 마다 작은 값을 저장해준다.

 

일단 10,001이라는 값으로 초기화 시켜놓고 d[0] = 0으로 초기화시켜놓는다.

3원으로 만들 수 있는 화폐 갯수를 저장하기 위해 d[j - arr[i]] 라는 점화식을 사용한다..

 

첫번째 화폐 단위는 3

d[3] = 1

d[6] = d[6-3] + 1 = 2

d[9] = d[9-3] + 1 = 3

... 로 저장이 된다.

 

두번째 화폐 단위는 6

d[6] = 2와 1중에 1이 저장

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = kb.nextInt();

        //m원을 만들기위한 dp 테이블 초기화
        int[] dp = new int[m+1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = arr[i]; j <= m; j++) {
                if(dp[j-arr[i]] != 10001) {
                    dp[j] = Math.min(dp[j], dp[j-arr[i]] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        if(dp[m] == 10001) System.out.println(-1);
        else System.out.println(dp[m]);
    }
}