[JAVA] 백준 2294번: 동전 2

https://www.acmicpc.net/problem/2294

2294번: 동전 2

✅ 골드 Ⅴ

 

🔶 풀이

N가지 종류의 동전이 주어지면 동전을 최대한 적게 사용해서 K원을 만들어라.

다이나믹 프로그래밍(dp) 문제로 아래의 조건만 신경써주면 딱히 어려운 게 없는 문제라고 생각한다.

 

1️⃣ 각각의 동전을 여러 개 사용할 수 있음

2️⃣ 정확하게 K원을 만들지 못 하면 -1을 출력함

 

예제로 점화식을 찾아보겠다.

 

1원 동전

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

 

5원 동전

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	1	0	0	0	0	2	0	0	0	0	3

 

12원 동전

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	1	0	0	0

 

각각의 동전으로 만들 수 있는 금액의 경우의 수를 다 dp 배열에 작성해주면 된다.

1원 동전은 1원부터 K원까지 가능하고, 5원 동전은 5원부터 15(K)원까지 가능하고, 12원 동전은 1원부터 12원까지 가능하다.

 

왜 5원짜리 동전이 만들 수 있는 금액의 경우의 수가 5, 10, 15가 아니고, 5원부터 15원까지인지 이해하지 못 할 수도 있다. 5원부터 15원까지 말한 이유는 다른 동전과 함께 사용했을 때 해당 금액을 만들 수 있기 때문이다. 

 

즉, 6원은 1원 + 5원으로 2개의 동전을 사용해서 만들 수 있다.

for (int j=coin; j<=K; j++) {
    dp[j] = Math.min(dp[j], dp[j-coin] + 1);
}

 

위와 같은 점화식을 사용할 때 주의할 점이 있다.

우선 최대한 적은 개수의 동전을 구해야하므로 dp 배열을 최대값으로 초기화해줄 것이다.

 

여기서 dp 배열의 최대값은 K 값의 최대 범위 10000에서 1을 더해준 값으로 10001을 해주면 된다.

K원을 만들기 위해서 최대한 많은 동전을 쓰는 경우는 1원만 사용해서 만든 경우이기 때문이다.

 

또한, dp[0]을 0으로 초기화해줘야된다.

dp[0]을 초기화해주지 않으면 위와 같은 점화식에서 모두 초기화해둔 10001로 나올 것이다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
		
        int[] dp = new int[K+1];
        Arrays.fill(dp, 10001);
		
        dp[0] = 0;
		
        for (int i=0; i<N; i++) {
            int coin = Integer.parseInt(br.readLine());
			
            for (int j=coin; j<=K; j++) {
                dp[j] = Math.min(dp[j], dp[j-coin] + 1);
            }
        }
		
        if (dp[K] == 10001) {
            System.out.println(-1);
        } else {
            System.out.println(dp[K]);
        }
    }
}