[ DP ] 효율적인 화폐 구성

난이도 : 중상  풀이시간 : 30분  시간제한 : 1초 

[ DP ] 효율적인 화폐 구성

N가지 종류의 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록하려고 한다. 이 때 각 화폐는 몇 개라도 사용가능하며 사용한 화폐의 구성은 같지만 순서가 다른 것은 같은 경우로 구분한다.

 

:: 입력 조건

 

• 첫째 줄에 N, M이 주어진다.(1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

 

:: 출력 조건

 

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

 

---

 

  내   코드  

점화식을 세울 때 

dp[j] = min(dp[j], dp[j-n[i]]+1);

이렇게 세우고

이게 성립하려면

dp[j]에 기본으로 설정 된 값이 0이면 안됨

 

그리고 내가 점화식을 잘못 세움 ,,, 

dp[j] = min(dp[j], dp[j-ns[i]] + dp[ns[i]]) < 이렇게 세움

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> arr;

int main(void) {
    // 정수 N, M을 입력받기
    cin >> n >> m;
    
    // N개의 화폐 단위 정보를 입력 받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
    vector<int> d(m + 1, 10001);

    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    d[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = arr[i]; j <= m; j++) {
            // (i - k)원을 만드는 방법이 존재하는 경우
            if (d[j - arr[i]] != 10001) {
                d[j] = min(d[j], d[j - arr[i]] + 1);
            }
        }
    }

    // 계산된 결과 출력
    if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
        cout << -1 << '\n';
    }
    else {
        cout << d[m] << '\n';
    }
}