[코드업] 2634 - 거스름돈 II

여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의 개발을 의뢰받았다.

이번에도 역시 자동판매기에서 이용자에게 거스름돈을 남겨줄 때, 거스름돈에 사용될 동전의 수를 가정 적게하는 것이다.

입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가지 수 그리고 동전의 종류가 들어온다.

여러분은 그 돈의 액수를 거슬러 주는 여러가지 방법들 중 가장 적은 동전은 몇개인지 구하는 프로그램을 작성해야 된다.

입력

첫 번째 줄에는 거슬러 줘야할 돈의 액수가 입력된다. (이 값은 10,000원 이하이다.)

다음 줄에는 그 나라에서 사용되는 동전의 종류의 수가 입력된다. (단 동전의 수는 10이하이다.)

마지막 줄에는 동전의 수 만큼의 동전 액수가 오름 차순으로 입력된다. (동전의 최대값은 10,000원 이하이다.)

모든 입력에 대해 답이 있음을 보장한다.

출력

최소의 동전의 수를 출력한다.

입력 예시

730
5
10 50 100 500 1250

출력 예시

6

---

#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 987654321;

int N;
int coin[11];
int coin_dp[10001];

int solve(int amount) {
    coin_dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        int minValue = INF;
        for (int j = 0; j < N; j++)
            minValue = min(minValue, i - coin[j] < 0 ? INF : coin_dp[i - coin[j]]);
            
        coin_dp[i] = 1 + minValue;
    }
    return coin_dp[amount];
}
int main() {
    int amount; 
    cin >> amount >> N;
    for (int i = 0; i < N; i++)
        cin >> coin[i];
        
    cout << solve(amount);
    return 0;
}