[백준] 11047번 : 동전 0

문제

 

---

풀이

 

거스름돈 문제는 여러가지가 있지만 이 문제처럼 특수한 경우에는 그리디 알고리즘을 적용할 수 있다.

그 특수한 경우가 무엇일까? 바로 모든 동전들의 가치가 배수관계일 때이다.

 

만약 가치가 1, 7, 10원인 동전 3개가 있고 14원을 거슬러 줘야 한다고 하자.

그리디 알고리즘을 적용하면 10원 1개, 1원 4개 총 5개의 동전을 사용하지만 최적해는 7원 2개 총 2개의 동전을 사용하는 것이다.

 

아무튼 이 문제는 모든 동전들의 가치가 배수관계이니 맘편하게 그리디 알고리즘을 적용하자.

가장 가치가 큰 동전부터 가치가 작은 동전 순서로 거스름돈과 비교하면 된다.

---

소스코드

 

#include <iostream>
using namespace std;

int coin[11];

int greedyCoin(int N, int K) {
    int cnt = 0;
    for (int i = N - 1; i >= 0; i--) { //큰 수부터
        if (K >= coin[i]) { //이 동전으로 거스름돈을 지불할 수 있음
            cnt = cnt + (K / coin[i]);
            K %= coin[i];
        }
    }
    return cnt;
}

int main() {
    int N, K;

    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> coin[i];
    cout << greedyCoin(N, K);
}