[백준/c++] 11047번: 동전 0

 

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

11047번: 동전 0

 

동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해 그 가치의 합을 K로 만들려고 한다. 필요한 동전 개수의 최솟값을 구하는 프로그램

 

동전 개수 최솟값을 구해야하므로 큰 동전부터 나눠줘야 한다. 배열의 뒤부터 차례대로 나눠주면 완료

#include <iostream>
#include <algorithm>
using namespace std;
int n, k, money[11], ans=0;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> money[i];
    
    for(int i=n-1; i>=0; i--){
        int m = k / money[i];
        k %= money[i];
        ans += m;
    }
    cout << ans << '\n';
    return 0;
}