[BOJ] 11047 - 동전 0 (C++)

문제

동전 o

코드

#include <iostream>

using namespace std;
int N, K;
int money[11];

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> money[i];

    int cnt = 0;
    for (int i = N-1; K != 0 or i >= 0; i--){
        if (money[i] > K) continue;
        else {
            cnt += K/money[i];
            K = K - (K/money[i])*money[i];
        }
    }
    cout << cnt;
    return 0;
}

접근

이 문제는 동전의 개수가 무한대이기 때문에 현재 사용할 수 있는 금액의 최대 개수를 사용하면 된다. 따라서 금액을 역순으로 살펴보면서 현재 남은 K보다 작은 경우에 한해 개수를 세고 금액을 감소시키면서 답을 찾으면 된다.