문제

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

---

입력

첫째 줄에 n, k가 주어진다.
다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

---

출력

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

---

풀이

제한조건

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

접근방법

DP

동전1 문제와 다르지 않다.

최대 동전의 수가 100으로 중복이 나오더라도, 별도로 처리할 필요없이 중복 상태로 두고 계산하면 된다.

차근차근 살펴보자.
dp[m]를 m원을 만들기 위해 필요한 동전의 최소 갯수라고 정의해보자.

동전 1개를 사용하여 만들 수 있는 금액은 어떤것들이 있을까?
바로 입력으로 주어지는 N가지 종류의 동전과 동일한 금액이다.

그럼 나머지 금액들은 어떻게 만들 수 있을까?
주어진 동전의 가치가 가장 낮은 동전이 L원이라고 가정하자.
우리는 L원 보다 비싼 동전만 가지고 있기 때문에 L원 이하는 만들 수 없다.

따라서 L원 이상의 금액만 만들 수 있다.

for (int i = min; i <= K; ++i) {
	// ... 무언가의 코드 구현 필요!
}

이제 L원부터 1원씩 증가시키며 K원을 만드는 과정까지를 살펴보자.
L+1원을 만들고자 한다면, 특정 종류의 동전의 가치(S)를 L+1원에서 한 번 빼보자.
그럼 L+1-S원을 만들 수 있는가?

만들 수 있다면 dp[L+1-S]원을 만드는 최소 동전의 개수 + 방금 사용한 S원 동전 1개를 이용해 최소 개수를 사용할 수 있다.

즉 아래와 같이 확장시켜 정의할 수 있다.

for (int i = min; i <= K; ++i) {
	for (int j = 0; j < N; ++j) {
    	if (i - coins.get(j) < 0)
        	continue;
        dp[i] = Math.min(dp[i], dp[i - coins.get(j)] + 1);
	}
}

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;

public class Main {
	static int N, K;
	static List<Integer> coins = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		// input
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		K = stoi(inputs[1]);

		int[] dp = new int[100001];
		Arrays.fill(dp, 100001);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; ++i) {
			int value = stoi(in.readLine());
			coins.add(value);
			dp[value] = 1;
			min = min < value ? min : value;
		}

		for (int i = min; i <= K; ++i) {
			for (int j = 0; j < N; ++j) {
				if (i - coins.get(j) < 0)
					continue;
				dp[i] = Math.min(dp[i], dp[i - coins.get(j)] + 1);
			}
		}
		System.out.println(dp[K] == 100001 ? -1 : dp[K]);

	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}