[백준] 동적 프로그래밍 - 2294번 동전 2 (Java)

문제링크

2294번: 동전 2

 

접근한 방법

• 동적 프로그래밍

---

문제 풀이 방법

• $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

 

출처 : 2020/11/10 - [알고리즘/이것이 코딩테스트다] - Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java)

 

---

 

소스코드

package baekjoon.dp;
import java.io.*;
import java.util.StringTokenizer;

public class Q_2294_Coin22 {
    public static int solution(int[] coin, int k){
        int[] a = new int[k + 1];
        
        for(int i=1; i<=k; i++)
            a[i] = 10001;

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

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

        return a[k];
    }
    
    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 k = Integer.parseInt(st.nextToken()); // 가치의 합

        int[] coin = new int[n];
        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        bw.write(solution(coin,k)+"\n");

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