[백준 알고리즘/C++] 11047 동전 0

 

 

동전을 적절히 더하여 K로 만들 때 필요한 동전 개수의 최솟값을 구하는 문제

 

1원 ~ 50000원 동전을 적절히 더해서 4200을 만들면 되는데, 최소한의 동전만 써야 한다

 

1원짜리 4200개, 5원짜리 840개, 10원짜리 420개 ···

당연히 액수가 큰 동전을 많이 쓸수록 동전의 개수가 적어진다

 

내림차순으로 계산하면

50000 X, 10000 X, 5000 X, 1000원짜리 4개, 500 X, 100원짜리 2개

총 6개의 동전으로 4200을 만들 수 있다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, k;
    int arr[11];
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
 
    int temp, res = 0;
    temp = k;
    for (int i = n; i > 0; i--) {
        res += temp / arr[i];
        temp %= arr[i];
    }
 
    cout << res;
}

 

n번째 동전부터 역순으로 계산해주면 됨