효율적인 화폐 구성

문제

N종류의 화폐를 이용하여 합이 M이 되도록하는 화폐의 최소 개수 구하기

입력

N, M (1<=N<=100, 1<=M<=10,000)
N개의 줄에 화폐의 가치가 주어짐

출력

경우의 수 X 출력, 불가능한 경우 -1 출력

풀이

그리디 알고리즘의 거스름돈 문제와 비슷해보이지만, 매번 가장 큰 화폐부터 처리하는 방법으로 해결할 수 없기 때문에 다이나믹 프로그래밍을 사용해야함.

적은금액부터 순서대로 확인하면서 이전 금액을 만들 수 있는 경우+1과 현재값의 경우의 수를 비교하여 최솟값을 구하기

점화식 예) a2=min(a2, a1+1)
두번째 값의 경우의 수는 바로 이전의 값의 경우의 수 +1과 비교하여 최솟값

#include<iostream>
#include<vector>
#include<algorithm>

#define MAXN 101
#define MAXM 10001

using namespace std;

int money[MAXM]; //만들수있는 최소 화폐개수
int bill[MAXN]; //화폐 종류


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	fill(money, money + MAXN, MAXM); //최대값으로 초기화

	int N, M;
	cin >> N >> M;


	for (int i = 0; i < N; i++) {
		cin >> bill[i];
	}

	money[0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = bill[i]; j <= M; j++) {
			money[j] = min(money[j], money[j - bill[i]] + 1);
		}
	}

	if (money[M] == MAXM) {
		cout << -1;
	}
	else {
		cout << money[M];
	}



	return 0;
}