그리디 알고리즘은 매 순간 최선의 선택으로 최적의 결과를 도출하고자 하는 알고리즘이다. 적절한 문제에 적용한다면 모든 경우를 조사하는 방법보다 더 빠르게 결과를 확인할 수 있다. 아래는 입력으로 들어온 동전을 사용해서 k원을 구하는 데 필요한 동전 수의 최소를 구하는 문제의 코드이다.

<aside> 💡 매 경우 가능한 큰 값의 동전을 사용하는 것이 유리하다. 이용할 수 있는 동전은 서로 약수/배수 관계이기 때문에 항상 값어치가 큰 동전을 사용하는 것이 최적임이 보장된다. 따라서 모든 순간에 최대의 동전을 사용한다면 궁극적으로 k원을 만드는 데 필요한 최소 동전 개수를 구할 수 있다.

</aside>

#include <iostream>
#include <vector>

using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    vector<long long> coin(14);
    long long a, coins;

    cin>>n>>k;
    a = n-1;
    coins = 0;

    for(int i = 0; i<n; i++){
        cin>>coin[i];
    }

    while(k > 0){
        if(coin[a] > k){
            a--;
            //cout<<k<<'r'<<coin[a]<<'\\n';
        }
        else if(coin[a] <= k){
            k -= coin[a];
            coins++;
            //cout<<k<<'s'<<coin[a]<<'\\n';
        }
    }

    cout<<coins;

    return 0;
}