N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
2 15
2
3
5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 효율적인 화폐 구성
public class DP_04 {
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 m = Integer.parseInt(st.nextToken());
int[] coins = new int[n];
int[] d = new int[m + 1];
// 화폐 입력
for (int i = 0; i < n; i++) {
coins[i] = Integer.parseInt(br.readLine());
}
// DP 테이블 초기화
for (int i = 0; i < m + 1; i++) {
d[i] = 10001;
}
// 점화식에 따라 반복문 실행
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j < m + 1; j++) {
d[j] = Math.min(d[j], d[j - coins[i]] + 1);
}
}
// 만들 수 없는 경우 -1 출력
if (d[m] == 10001) {
System.out.println(-1);
} else {
System.out.println(d[m]);
}
}
}