[이것이 코딩 테스트다] 효율적인 화폐 구성

❓ 문제 ❓
N 종류의 화폐를 통해 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 해라

💯 문제 풀이 💯
점화식 a = min(a, a-k+1)을 통해 풀이한다. (K는 화폐의 단위)

#include <iostream>
#include <vector>
using namespace std;
int dp[10001];
int money[101];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> money[i];
	}

	for (int i = 1; i <= m; i++) {
		dp[i] = 10005;
	}

	for (int i = 0; i < n; i++) {
		for (int j = money[i]; j <= m; j ++) {
			if (dp[j - money[i]] != 10005) {
				dp[j] = min(dp[j], dp[j - money[i]] + 1);
			}
		}
	}
	if (dp[m] == 10005) cout << -1;
	else cout << dp[m];
}