[백준 BOJ 2294] 동전 2

백준 링크

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

풀이

• DP문제이다
• d[i] : i원을 만드는 최소 동전 개수
• 각 동전을 입력받을때마다 (현재 동전)<=j<=k에서 d[j] = min(d[j], d[j-a[i]] + 1) 으로 갱신한다

코드

#include<iostream>
#include<string.h>
using namespace std;

int n, k, a[105], d[200005];
const int MAX = 100005;

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

	for (int i = 0; i < 20005; i++) d[i] = MAX;

	d[0] = 0;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = a[i]; j <= k; j++) {
			if (d[j - a[i]] + 1 < d[j]) {
				d[j] = d[j - a[i]] + 1;
			}
		}
	}
	if (d[k] == MAX) cout << -1;
	else cout << d[k];
}