[백준] 2294번

💻 C++ 기반

동전 2
https://www.acmicpc.net/problem/2294

✔️ 동전 문제 풀이 참고
✔️ dp 배열을 초기화할 때 k의 최댓값보다는 큰 값으로 초기화해야 함

#include <cstdio>
#include <algorithm>

#define MAX 101
#define MAX_K 10001
#define MAX_VALUE 100001

using namespace std;

int values[MAX];
int dp[MAX_K];

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &values[i]);
    }

    fill(dp, dp + MAX_K, MAX_VALUE);

    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = values[i]; j <= k; j++)
        {
            dp[j] = min(dp[j], dp[j - values[i]] + 1);
        }
    }
    
    if (dp[k] == MAX_VALUE)
    {
        printf("-1");
    }
    else
    {
        printf("%d", dp[k]);
    }
    return 0;
}