백준 2294: 동전2

다이나믹 프로그래밍을 사용하는 문제 d를 0부터 끝까지 순회하므로 만약 d[i]번째에 도달하는 경로가 없을 경우 이를 계산하지 않도록 유의하면서 if문을 짜줘야한다. j원에서 동전 값을 뺀 것이 0보다 크고 동시에  d[j - coin[i]] 또한 -1 (배열을 -1로 값을 설정했다.)이 아니어야 이전에 값이 메모라이징 됬었다는 것이고 처음 j원에 방문하는 것인지 아닌지를 판단해 준 후 가장 최소 값을 입력해준다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int coin[106];
int d[10006];
 
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> coin[i];
    for (int i = 0; i < 10006; ++i)
        d[i] = -1;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    for (int j = 1; j <= k; ++j)
    {
        if (j - coin[i] >= 0 && d[j - coin[i]] != -1){
            if (d[j] == -1)
                d[j] = d[j - coin[i]] + 1;
            else
                d[j] = min(d[j], d[j - coin[i]] + 1);
        }
    }
    cout << d[k] << '\n';
    return 0;
}