C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 2294번:동전2 답

//d[i] = i원을 만드는데 필요한 최소 동전의 개수

//d[i] = d[i-a[j]]+ 1 (d[i-a[j]] !=-1 : d[i-a[j]]==-1라면 애초에 이 값을 만들수가 없다는 뜻이므로 -1이면 안된다)

#include <iostream>
#include <algorithm>
using namespace std;
int n,k, a[101], d[100001],ans=-1;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++)
        d[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            if (a[i] <= j && d[j - a[i]] != -1)
                if (d[j] > d[j - a[i]] + 1 || d[j] == -1)
                    d[j] = d[j - a[i]] + 1;
    cout << d[k] << '\n';
}