백준 2294: 동전 2 [Java] - 포포

문제

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

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

입력

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

출력

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

예제 입력 1 

3 15
1
5
12

예제 출력 1 

3

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

2294번: 동전 2

---

이 문제는 K원을 도달하는데 필요한 동전의 최소 개수를 구하는 문제다.
예를 들어 K = 10이고 동전이 1원, 3원, 5원이 있다고 해보자. 

coin \ k	1	2	3	4	5	6	7	8	9	10
1원	1	2	3	4	5	6	7	8	9	10
3원			1			2			3
5원					1					2

이 경우 5원짜리 2개를 사용하는 것이 최소 동전 개수가 되겠다.
1원부터 10원까지 검사하는데, 
1원만 사용하는 상황에서는 10원을 만들기 위해 10개의 동전이 필요했다.

하지만 3원을 사용하면서 3원 * 3개 + 1원 * 1개로 총 4개의 동전이 필요해졌고
5원을 사용한 순간 5원 * 2개로 총  2개의 동전으로 해결할 수 있었다.

1원을 사용하다가 3원을 사용했을 때 10원을 만드는 동전 개수를 최소값으로 갱신하는 방법은
아래의 점화식을 사용하는 것이다.

dp[10] = Math.min(10, dp[10-3] + 1)

Bottom-Up 방식이므로 dp[10-3] = dp[7]은 이미 최소값으로 갱신이 되어있을 것이다.

dp[1] = 1
dp[4] = Math.min(4, dp[4-3] + 1) = dp[1] + 1 = 2
dp[7] = Math.min(7, dp[7-3] + 1) = dp[4] + 1 = 3
dp[10] = Math.min(10, dp[10-3]+1)  = dp[7] + 1 = 4

 

정리해보면, 3원을 사용하는 순간 10원 만드는 동전의 최소 개수는 4가 되는 것이다.

따라서 상향식 풀이의 점화식은 다음과 같다.

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

제출한 코드

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

public class Main {
    static int n, k;
    static int[] coins;
    static int[] dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        coins = new int[n + 1];
        dp = new int[k + 1];

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

        Arrays.sort(coins);
        Arrays.fill(dp, 100001);

        dp[0] = 0;

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

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

---

해보진 않았지만 하향식으로 풀어봐도 괜찮을 듯 싶다.

10원 만드는 동전의 최소 개수 = Math.min(9원을 만드는 동전의 개수, 7원을 만드는 동전의 개수) + 1

이렇게 구할 수 있을 것이다.
그렇다면 또 다시
9원을 만드는 동전의 최소 개수 = Math.min(8원을 만드는 동전의 개수, 6원을 만드는 동전의 개수) + 1 
7원을 만드는 동전의 최소 개수 = Math.min(6원을 만드는 동전의 개수, 4원을 만드는 동전의 개수) + 1
이렇게 메모이제이션을 이용해 역순으로 찾아가는 것이다.

풀이는 생략..