BOJ 11047번, 동전 0

문제 풀이에 사용된 것은 Greedy Method로, 매 순간마다 최적의 해를 추구하는 방법이라 저렇게 이름이 붙었습니다.

편의점이나 카페에서, 잔돈을 거슬러 주는 방법과 유사합니다.
되게 직관적이죠.

예를 들어, 490원을 10원, 50원, 100원, 500원으로 남겨주는 방법의 개수를 찾는다면?

다음과 같은 방법이 있을 수 있습니다.
a. 10원짜리 49개.
b. 100원짜리 4개, 10원짜리 9개
c. 100원짜리 4개, 50원짜리 1개, 10원짜리 4개
등등...

이미 깨달으신 분도 계시겠지만, 큰 돈부터 먼저 채워나가면 동전의 개수를 최소화할 수 있습니다. 아래는 그 소스코드 입니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
int main() {
    vector<LL> v;
    LL n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        LL temp; cin >> temp;
        v.push_back(temp);
    }
    reverse(v.begin(), v.end());
    LL idx = 0;
    LL gesu = 0;
    while (m != 0) {
        while (true) {
            if (m >= v[idx]) {
                m -= v[idx];
                gesu++;
            }
            else {
                idx++;
                break;
            }
        }
    }
    cout << gesu;
    return 0;
}