[백준] 2294 - 동전 2

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

2294번: 동전 2

동전 k일때 동전의 최소 개수를 구하는 문제입니다. 저는 0원부터 k원까지 dp를 완성해서 푸는 방식으로 해결하였습니다. dp를 모두 INF로 초기화시키고 1원부터 k원까지 dp를 돌려줍니다. dp[i]를 초기화할때 동전 벡터를 전부 돌려가면서 dp[i]랑 dp[i - 동전] 을 비교해 더 작은 값을 저장합니다. 이때 i - 동전이 0 이상일때와 dp가 INF가 아닐 때만 초기화 해줍니다. 그리고 마지막에 dp가 INF면 도달할 수 없는 값이므로 -1을 출력하고 아니면 dp[k]를 출력합니다.

#include <iostream>
#include <vector>
#define MAX 10001
#define INF 100000000
using namespace std;

vector<int> v;
int dp[MAX];
int n, k, tmp;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }

    dp[0] = 0;
    for (int i = 1; i <= k; i++)
        dp[i] = INF;

    for (int i = 1; i <= k; i++)
        for (auto j : v)
            if (i - j >= 0 && dp[i - j] != INF)
                dp[i] = min(dp[i], dp[i - j] + 1);

    if (dp[k] == INF)
        cout << "-1\n";
    else
        cout << dp[k] << "\n";

    return 0;
}