[이.코.테] Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java)

효율적인 화폐 구성 문제 (교재 99p)

난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

 

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화페는 몇개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

 

입출력 조건)

입력 조건	- 첫째 줄에 N, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 10,000)  - 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.
출력 조건	- 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.  - 불가능할 때는 -1을 출력한다.

입출력 예시)

입력 예시	출력 예시
2 15 2 3	5
3 4 3 5 7	-1

---

문제 풀이 방법

• $a_{i}$ : 금액 i를 만들 수 있는 최소한의 화폐 개수
• $a_{i-k}$ : 화폐의 단위를 k라고 했을 때, 금액 (i-k)를 만들 수 있는 최소한의 화폐 개수
                (i-k : 금액 i에서 화폐의 단위 k를 뺀 금액)

이 문제를 점화식으로 표현해보면 아래와 같다.

$a_{i-k}$를 만드는 방법이 존재 O	$a_{i} = min(a_{i}, a_{i-k}+1)$	화폐 단위 작은 것부터 계산했을 때 얻어진 $a_{i}$와 (i-k)의 화폐 개수에 1(k가 더해지는 것 : 횟수 1)더한 것 중 최소
$a_{i-k}$를 만드는 방법이 존재 X	$a_{i} = 10,001$

예시

n = 3

화폐단위 k = {2,3,5}

m = 7

* 반복문의 처음 시작은 화폐 단위부터 시작

 

step 0 초기화

• 각 인덱스에 해당하는 값으로 10,001을 설정한다. 10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다. (∵M의 크기가 10,000이 최대이므로, 10,001로 설정)
• i = 0의 경우 (인덱스가 0), 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 0으로 설정

i	$a_{i}$
0	0
1	10,001
2	10,001
3	10,001
4	10,001
5	10,001
6	10,001
7	10,001

step 1 화폐단위 : 2

 

i	$a_{i}$	설명
0	0	화폐를 하나도 사용하지 않았을 때
1	10,001	화폐 단위가 2부터 시작하여 검사하지 않으므로, 10,001로 고정되어있음
2	1	min(10001, $a_{2} = a_{0} + 1 $) = min(10001, 1) = 1
3	10,001	min(10001, $a_{3} = a_{1} + 1 $) = min(10001, 10002) = 10001
4	2	min(10001 , $a_{4} = a_{2} + 1 $) = min(10001, 2) = 2
5	10,001	min(10001, $a_{5} = a_{3} + 1 $) = min(10001, 10002) = 10001
6	3	min(10001 , $a_{6} = a_{4} + 1 $) = min(10001, 3) = 3
7	10,001	min(10001, $a_{7} = a_{5} + 1 $) = min(10001, 10002) = 10001

 

step 2 화폐단위 : 3

i	$a_{i}$	설명
0	0	화폐를 하나도 사용하지 않았을 때
1	10,001	화폐 단위가 3부터 시작하여 검사하지 않으므로, 10,001로 고정되어있음
2	1	화폐 단위가 3부터 시작하여 검사하지 않으므로, 1로 고정되어있음
3	1	min(10001, $a_{3} = a_{0} + 1 $) = min(10001, 1) = 1
4	2	min(2 , $a_{4} = a_{1} + 1 $) = min(2, 10002) = 2
5	2	min(10001, $a_{5} = a_{2} + 1 $) = min(10001, 2) = 2
6	2	min(3 , $a_{6} = a_{3} + 1 $) = min(3, 2) = 2
7	3	min(10001, $a_{7} = a_{4} + 1 $) = min(10001, 3) = 3

step 3 화폐단위 : 5

i	$a_{i}$	설명
0	0	화폐를 하나도 사용하지 않았을 때
1	10,001	화폐 단위가 5부터 시작하여 검사하지 않으므로, 10,001로 고정되어있음
2	1	화폐 단위가 5부터 시작하여 검사하지 않으므로, 1로 고정되어있음
3	1	화폐 단위가 5부터 시작하여 검사하지 않으므로, 1로 고정되어있음
4	2	화폐 단위가 5부터 시작하여 검사하지 않으므로, 2로 고정되어있음
5	1	min(2, $a_{5} = a_{0} + 1 $) = min(2, 1) = 1
6	2	min(2 , $a_{6} = a_{1} + 1 $) = min(2, 100002) = 2
7	3	min(3, $a_{7} = a_{2} + 1 $) = min(3, 2) = 2

 

소스 코드

package exam08_dynamic_programming;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q4_Money {
    public static int solution(int[] k, int m) {
        int[] a = new int[m+1];

        Arrays.fill(a,10001);
        a[0] = 0;

        for(int i=0 ; i<k.length ; i++){
            for (int j = k[i]; j < m + 1; j++) {
                a[j] = Math.min(a[j], a[j - k[i]] + 1);
            }
        }

        if(a[m] == 10001)
            a[m] = -1;

        return a[m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 화폐 종류의 수
        int m = Integer.parseInt(st.nextToken()); // 합
        int[] k = new int[n]; // 화폐의 종류

        for (int i = 0; i < k.length; i++) {
            k[i] = Integer.parseInt(br.readLine());
        }
        bw.write(solution(k, m)+"\n");

        br.close();
        bw.close();
    }
}

 

---

백준 동일한 문제

2294번: 동전 2