[알고리즘] 동전 2(백준2294번)_골드5_dp

문제링크

📝 문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3 15
1
5
12

예제 출력 1

3

---

🔍 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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[] coin = new int[n];            // 동전의 가치를 담을 배열
        long[] dp = new long[k+1];          // dp[x원] 의 가치를 만들 때 가장 적게 사용하는 동전의 개수
        long INF = Integer.MAX_VALUE;
        Arrays.fill(dp, INF);               // dp를 무한대로 채워준다. 나중에 min 값을 갱신해주기 위함!

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

        /**
         * 점화식!
         * 규칙을 쉽게 찾기 위해서 동전의 가치는 1, 2, 3으로 두고 dp[6] 까지만 계산해본 후 규칙을 찾아보았다.
         */
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = coin[i]; j <= k; j++) {
                if (j == coin[i]) dp[j] = 1;        // dp[j](구하려는 가치)와 coin[i](동전의 가치)가 같다면 1개의 동전으로 만들 수 있다.
                dp[j] = Math.min(dp[j], dp[j - coin[i]] + dp[coin[i]]);
            }
        }

        /**
         * 출력
         * dp값이 갱신되지 않았다는 것은 주어진 동전으로 만들 수 없다는 뜻이므로 -1을 반환하도록 한다.
         */
        if (dp[k] == INF) System.out.println(-1);
        else System.out.println(dp[k]);
    }
}

• 규칙을 쉽게 찾아보기 위해 동전의 가치는 1, 2, 3으로 두고 dp는 6까지만 계산해보았다.
• 어떠한 가치를 만들기 위해서 최소한으로 들어가는 동전의 개수에는 항상 동전의 최댓값이 들어간다는 것을 알 수 있다.
• 따라서 6원을 1, 2, 3원으로 만든다고 가정하면 3원은 무조건 하나 이상 사용할 것이므로 dp[6 - coin[3]] 으로 3원의 동전 가치를 빼주고 dp[3]의 개수 + 사용한 동전 하나(dp[coin[i]])를 더하는 것이 점화식이 된다!
• 이 때 dp[coin[i]]는 항상 1이기 때문에 점화식에서 dp[coin[i]] 는 1로 치환해도 된다!