[백준] DP 2294번 동전2 C++풀이

문제

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

 

이전 포스트의 동전1과 같은 DP 문제, 이번엔 주어진 목표 금액과, 주어진 동전의 개수를 최소로했을때 몇갠지 세는 것이다. 

 

 

---

풀이

동전1과 달리 0원일때는 DP[0] = 0으로 초기화, 그리고 각 동전마다 DP배열에 1씩 추가하는 형태로 나아간다. 이때 DP배열이 추가하는 것보다 작으면 냅둬서 최소 개수를 구해나간다.

이때 DP배열은 미리 최댓값INF을 대입해놔서, 만들어질 수 없는 값임을 초기화 시킨다.

 

 

---

#include <bits/stdc++.h>

using namespace std;

const int INF = 10001;
int n, k;
vector <int> coin;
int dp[10001];
int main(){
    cin >> n >> k;
    int num;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        coin.push_back(num);
    }
    fill(dp, dp+10001, INF);
    dp[0] = 0;
    for (int i = 0; i < coin.size(); ++i) {
        for (int j = coin[i]; j <= k; ++j) {
            dp[j] = min(dp[j], dp[j - coin[i]] + 1);
        }
    }
    if(dp[k] == INF) cout << -1;
    else cout << dp[k];
}

 

DP문제는 유형이 참많아서 까다롭다...