[C++] 백준 11047번 동전 0

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

풀이

매순간 가치가 가장 높은 동전을 이용해서 최대한 K에 가까운 금액을 만든다.
예를 들어, K가 1100이고 동전의 가치가 100, 500 이라면
첫번째로 가장 가치가 높은 500원 동전으로 1000을 만들고, 그 다음으로 가치가 높은 100원 동전으로 남은 100을 만든다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    
    int coin[10];
    for(int i=0; i<N; i++) cin >> coin[i];
    
    int ans = 0;
    for(int i=N-1; i>=0; i--) {
        if(coin[i] > K) continue;
        ans += K / coin[i];
        K %= coin[i];
    }
    
    cout << ans;

    return 0;
}