[그리디] 백준 문제풀이 - 동전 0

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

11047번: 동전 0

 

#include 
#include 
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    vector Coins(N, 0);
    for(int i=0; i<N; i++){
        cin >> Coins[i];
    }
    int answer = 0;
    for(int i=N-1; i>=0; i--){
        if(K >= Coins[i]){
            answer += K/Coins[i];
            K %= Coins[i];
        }
    }
    cout << answer << '\n';
    return 0;
}

 

동전의 종류에 대한 숫자 N과 맞추고자하는 금액 K가 주어지고, 

각 동전의 가치가 주어졌을 때 필요한 동전의 최소 개수를 구하는 문제다.

가장 큰 단위의 동전부터 가치가 낮은 동전 순으로 그때그때 최선의 솔루션을 구해나가는 전형적인 그리디 알고리즘으로 해결할 수 있었다.