[JAVA/백준 골드5] #2294 동전 2

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

🔒 골드5 - #2294 동전 2

 

📌 테스트케이스 추가 힌트

2 15
3
5

= 3

2 15
2
1

= 8

 

✍️ 풀이법

 

대표적인 DP 문제이고,  이 전 포스트인 동전 1 문제와 비슷하게 생각할 수 있다.

 

DP 문제를 풀 때, 가장 먼저 고려해야 할 것은

캐싱을 통한 점화식 도출이다.

 

 

캐싱을 위해 DP 테이블을 그려보면,

가로축에 K원이 되기 위한 가치를 나열할 수 있다.

 

그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자.

 

먼저, 1원짜리 동전을 추가해 준다.

첫 동전 만으로는 점화식을 도출하기 어려우므로, 다음 동전으로 넘어간다.

 

5원짜리 동전을  추가해 주게 되면, 4원까지는 캐시에 영향을 미치지 않는다.

 

이후, 5원을 만들 때부터는 5원짜리 동전을 사용할 수 있게 되므로, 사용하는 동전의 개수가 줄게 된다.

 

따라서, 5원짜리 동전을 하나 이상 사용해서 만들 경우를 구해준다.

 

먼저 5원을 만드는 경우.

5원을 하나 이상 사용하기 때문에,

만들고자 하는 값 5에서 현재 동전의 가치인 5를 빼주고, 그 값을 캐시에서 찾는다.

 

이 말은 즉, dp [5 - 5]를 찾아내고 5를 하나 사용했기 때문에 1을 더해준다.

 

따라서 여기까지만 보았을 때의 점화식은, 

dp [ i ] = dp [ i - coin [index] ] + 1

 

 

 

 

마찬가지로 10원 이상을 만들 때, 5원짜리 동전을 2개 이상 사용할 수 있으므로, 다음과 같이 채워지게 된다.

 

위의 점화식을 토대로 12원을 만드는 경우를 보면,

만들고자 하는 12원에서, 현재 동전을 하나 포함했기 때문에 동전의 가치를 빼준다. 12-5=7.

따라서 dp [7]에 1을 더하면 4가 도출된다.

 

dp [12] = 4

 

나머지 경우도 마찬가지로 채워주면 된다.

 

 

다음으로 12원짜리 동전을 추가한다.

 

12원 역시 위의 점화식으로 값을 도출하면,

 

13원을 만들고자 할 때,

만들고자 하는 13원에서, 현재 동전을 하나 이상 포함하므로, 13-12=1.

dp [1] + 1 = 2의 값을 도출한다.

 

14 역시

14-12=2 이므로,

dp [2] + 1 = 3의 값이 나온다.

 

그리고 가장 중요한 15를 보자.

 

만들고자 하는 15에서 12를 하나 이상 포함하므로, 15-12=3.

dp [3] = 3  이므로

dp [15] = 3+1 = 4의 값. 즉, 원래 저장되어 있던 3의 값보다 큰 값이 나오게 되므로,

 

기존 캐시의 값과 비교해서 최솟값을 도출해야 한다.

 

 

따라서 최솟값을 도출하는 점화식은 다음과 같이 도출할 수 있다.

dp [ i ] = Math.min( dp [ i ], dp [ i - coin [index] ] + 1)

 

하지만 Math.min을 사용하게 되면, 배열 선언 시 초기화 값인 0의 값이 계속 들어가게 될 것이다.

 

이 예시에서는, 첫 동전이 1원이었기 때문에 두 번째 동전과 세 번째 동전에서 문제가 발생하지 않지만,

테스트케이스 추가 힌트를 보며,  어떻게 해결해야 할지 감을 잡아보자.

 

2 15
3
5

= 3

 

첫 동전인 3원의 경우는 임의로 위 사진과 같이 채울 수 있다.

 

두 번째 동전인 5원을 추가하면, 5원이 사용되기 전까지는 이 전의 캐시를 가져온다.

 

 

여기서 5원을 만들기 위해, 점화식 dp [ i ] = Math.min( dp [ i ], dp [ i - coin [index] ] + 1)를 사용하게 되면,

 

5원을 1개 사용하는 경우가 있으므로, 답이 1이 되어야 하지만

Math.min에 의해 이전 캐시 값인 0이 채워지게 된다.

 

 

그렇다면 0이 아닌, 1이 채워지게 하기 위해서는 어떻게 해야 할까?

방법은 생각보다 간단하다.

 

0이 채워지는 이유는 배열의 초기값이 0인데 Math.min을 사용하기 때문이다.

 

따라서, 배열의 초기 값을 큰 값으로 초기화해주면 문제는 해결된다.

 

해당 문제는 "동전의 가치는 100,000보다 작거나 같은 자연수이다"라는 조건이 있으므로, 100,001로 초기화해주면 문제를 해결할 수 있다.

 

 

 

 

 

 

 

🗝️ JAVA 풀이

import java.util.Arrays;
import java.util.Scanner;

public class baekjoon2294 {

    static int K;
    static int[] dp;
    static int[] coin;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        K = sc.nextInt();
        coin = new int[N];
        dp = new int[K + 1];
        Arrays.fill(dp,100001);
        
        for (int testCase = 0; testCase < N; testCase++) {
            coin[testCase] = sc.nextInt();
        }

        solve();
    }

    public static void solve() {

        dp[0] = 0;

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

        if (dp[K] == 100001) {
            dp[K] = -1;
        }
        System.out.println(dp[K]);
    }
}