[Java] 백준 2294 : 동전 2

문제 링크

1.

이전에 풀었던 동전 1과 유사한 문제.

해당 문제의 풀이를 보고 복습하며 풀었다.

 

 

2.

동전 1 문제의 해설을 보고 이 해설을 보도록 하자.

 

차이점은 동전 1에서는 k 원을 만들 수 있는 모든 경우의 수를 구하지만,

동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다.

 

이를 위해서 다음과 같은 점화식을 세운다.

 

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

 

 

유의할 점은 다음과 같다.

1. dp 배열을 모두 100001로 초기화 한다.

사용한 동전의 개수가 최악일 경우 100,000개이다. (동전의 가치가 최대 100,000원이기 때문이다.)

따라서 이 최대 + 1인 100001로 초기화한다.

 

2. dp[0] = 0이다.

1원의 동전으로 1원을 만들 수 있는 경우의 수는 0원을 만들 수 있는 경우의 수 + 1이다.

즉 점화식의 구조를 따르기 위해 dp[0] = 0으로 초기화한다.

 

3. dp[k] = 100001이면 해당 금액을 만들 수 없다는 의미이므로 -1을 출력한다.

 

3.

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

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

        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] coin = new int[n];
        for (int i = 0; i < n; i++) {
            coin[i] = sc.nextInt();
        }

        int[] dp = new int[k + 1];
        Arrays.fill(dp, 100001);
        dp[0] = 0;

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

        System.out.println(dp[k] == 100001 ? -1 : dp[k]);
        sc.close();
    }
}

 

 

4.

 

[참고] http://bitly.kr/LXxJFX2n2x2R