[Java] 백준 동전 2

1. 문제분석

동전 n가지가 존재하고 적당하게 사용해서 합이 k원이 되는 동전 개수의 최솟값을 구하는 문제다.

기존 최댓값을 구하는 문제에서 최솟값을 구하는 문제이므로 Math.min을 사용한다.

 

이번 문제의 핵심은 인덱스 활용이다.

인덱스를 구하고자하는 가치로 생각해서 0부터 k까지 구하면 된다.

 

이제 차례대로 구해보자. 테스트 케이스 1의 경우를 보겠다.

동전은 총 3개, 1, 5, 12를 가지고 있고 원하는 가치는 15원이다.

먼저 동전 1을 쓰는 경우다. 1부터 15까지 동전 개수 또한 1개 ~ 15개가 된다.

 

중요한 건 다음 동전, 5의 경우이다.

5가 된다면 기존 DP[5]의 경우 5가 아닌 1이 들어가는 것이 맞다(DP[IDX], IDX를 가치로 보면 된다.)

즉, 구하고자 하는 것은 DP[현재 idx - 동전의 가치]부터 구하면 된다. 

 

표를 만들어서 한번 보자.

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

헷갈리지 않게 나머지 배열은 채우지 않았다.

5의 경우를 먼저 보자. 5를 넣으면 1이 되므로 기존 5개에서 1개로 줄어든다.

이번에는 idx 10의 경우를 보자. DP[10 - 5] = 즉, 5개에서 1개를 추가해주면 된다. 

마찬가지로 쭉 가다가 DP[15-5] = 2개에서 1개를 추가해주면 된다.

 

이번에는 12의 경우를 보자. 초기와 동일하게 DP[12 - 12]에서 1개를 추가한 것이다.

하지만 15의 경우, 원래 DP[15 - 12]에서 1을 더한 4가 나와야하지만 위에서 동전 3개를 쓰는 경우가 존재하므로 3이 된다.

이제 우리가 원하는 것을 다 구했으니 구현을 해보자.

2. 구현

import java.io.*;
import java.nio.Buffer;
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 size = Integer.parseInt(st.nextToken());
        //원하는 가격
        int price = Integer.parseInt(st.nextToken());
        //배열 크기
        int[] arr = new int[size];
        int[] dp = new int[price+1];
        for(int i = 0; i<size; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(dp, 100001);

        // dp배열은 해당 동전을 가장 적게 사용하는 수
        dp[0] = 0;

        for(int i = 0; i<size; i++){
            //만약 가장 작은 동전이 3인데 1을 구할 필요가 있나? 패스.
            for(int j = arr[i]; j<price+1; j++){
                // 현재 dp에 저장된 값과 새로운 동전 1개가 들어갔을 때
                dp[j] = Math.min(dp[j],dp[j-arr[i]] + 1);
            }
        }
        if(dp[price] == 100001){
            System.out.println(-1);
        }
        else{
            System.out.println(dp[price]);
        }
    }
}

동전은 1~100,000까지의 가치를 가진다. 그러므로 100,001이면 현재 동전으로 구할 수 없는 것이다.

초반에 DP[j - arr[i]] + 1이 헷갈릴 것 이다. 위에서 말한 것을 그대로 표현한 경우이므로 for문을 직접 적어보면서 풀면 이해하기 더 쉬울 것이다.

3. 마무리

결국 답을 본 문제지만 답을 봐도 이해가 가지 않았다.

왜 dp를 저렇게 표현하지 싶었지만 많은 똑똑한 사람 덕에 문제를 해결할 수 있었다.