[다이나믹 프로그래밍] 문제 이름 : 효율적인 화폐 구성

문제 설명

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

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

 

입력 조건- 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)- 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

 

출력 조건- 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.- 불가능할 때는 -1을 출력한다. 

 

사용 개념

다이나믹 프로그래밍

 

- 그리디에서 거스름돈 문제와 비슷한데, 주어진 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다.

- 따라서 그리디 알고리즘을 사용했던 것처럼 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없다.

 

문제 해결 아이디어 

점화식을 작성해보면,

 

금액 i를 만들 수 있는 최소한의 화폐 개수 = aᵢ

화폐의 단위(가치) = k

위의 해당 점화식을 주어진 모든 화폐 단위(가치)에 대하여 차례대로 적용하면 된다. 

이때 10,001은 특정 금액을 만들 수 있는 화폐 구성이 불가능하다는 의미 (M의 최대 크기가 10,000이므로 이보다 큰 수로 설정하면 됨)

 

코드 

import java.util.*;

public class Main {	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		int N = kbd.nextInt();
		int M = kbd.nextInt();
		
		// 화폐 단위(가치) 입력 
		int[] coins = new int[N];
		for(int i = 0; i < N; i++) {
			coins[i] = kbd.nextInt();
		}
		
		// 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화 
		// 방법1. for문
		// 방법2. Arrays.fill()
		int[] d = new int[M+1];
		Arrays.fill(d, 10001);
		
		// 다이나믹 프로그래밍 진행 (보텀업 방식)
		d[0] = 0;	// 0원을 만들기 위해 필요한 최소한의 화폐 개수 
		for(int i = 0; i < N; i++) {	// 모든 화폐 단위(가치)에 대하여 차례대로 반복함
			for(int j = coins[i]; j <= M; j++) {
				// (i-k)원을 만드는 방법이 존재하는 경우 
				if(d[j - coins[i]] != 10001) {
					d[j] = Math.min(d[j], d[j-coins[i]]+1);
				}
				
			}
		}
		
		// 계산 결과 출력
		if(d[M] == 10001) System.out.println(-1);	// 최종적으로 M원을 만드는 방법이 없는 경우 
		else	System.out.println(d[M]);
	}
}

 

추가 개념 정리

*Java에서 배열의 값을 특정 값으로 설정하기

방법1. for문을 사용

방법2. Arrays.fill()을 사용

참고) https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/Arrays.html