백준 2294 - 동전 2 (c++)

백준 2294 - 동전 2

문제 링크

생각 및 접근

• 동전의 가치가 주어지고, 여러번 골라서 그 가치의 합이 k원이 되게 하는 최소 동전의 갯수를 출력하고, k원을 만들 수 없다면 -1을 출력하는 문제다.
• dp[i]
  • i원이 되게 하는 최소 동전의 갯수를 저장한다.
• 동전을 총 n개 받는다고 하면, 1번 동전을 고려했을 때, 1~2번 동전을 고려했을 때, ... , 1~n번 동전을 고려했을 때를 탐색 한다. 즉, 동전을 하나씩 더 추가하면서 k원이 되게 하는 최소 동전의 갯수를 찾는 것이다.
• 추가할 동전의 값을 coin이라고 하면, j-for문을 돌려서 기존 dp[j]의 값과 dp[j - coin]에 coin을 추가했을 때의 값을 비교한다. dp[j] = min(dp[j], dp[j - coin] + 1);

    for (int j = coin; j <= k; j++) {
        dp[j] = min(dp[j], dp[j - coin] + 1);
    }

코드

#include <bits/stdc++.h>
#define _MAX 2147000000
using namespace std;

int n, k, coin, dp[10001];

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

    cin >> n >> k;

    for (int i = 1; i <= k; i++) {
        dp[i] = _MAX;
    }

    for (int i = 1; i <= n; i++) {
        cin >> coin;
        for (int j = coin; j <= k; j++) {
            dp[j] = min(dp[j], dp[j - coin] + 1);
        }
    }

    if (dp[k] == _MAX)  cout << -1;
    else                cout << dp[k];
}

채점 결과