백준 11047번: 동전 0

백준 11047번: 동전 0

11047번: 동전 0

그리디 알고리즘의 기초문제이다. 목표 값이 있고 동전들을 이용해서 그 값을 이루기 위해 최소의 개수를 사용해서 푸는 문제이다. 가장 최적의 방법을 찾아야하는데 동전수를 최소화하는것이 목적이니까 가지고 있는 동전 중에 사용할 수 있는 가장 큰 값의 동전을 먼저 사용하면 작은 동전들의 수를 최소화 할 수 있다. 큰 값의 동전들을 우선순위를 두어 사용하면 필요한 동전 개수의 최솟값을 구할 수 있다.

그리디 알고리즘은 항상 최적의 값을 가지는 것이 아니기 때문에 문제를 유의해서 보아야한다. 동전의 경우 각 동전들이 배수의 관계를 가지고 있어서 큰 가치의 동전들을 우선순위로 둘 수 있었지만 그렇지 않을 경우에는 고려해야할 사항이 많아져 그리디 알고리즘으로 풀기 어려울 것이다.

 

#include<iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int coin[11];
    int n, k;
    int num = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> coin[i];
    }
    int sum = k;
    for(int i = n-1; i >= 0; i--){
        if(sum >= coin[i]){
            int t = sum / coin[i];
            num += t;
            sum = sum - coin[i]*t;
        }
    }
    cout << num;
    return 0;
}