BOJ 11047 동전 0

boj 11047 동전 0

그리디 알고리즘을 활용하여 풀 수 있는 문제여서 적용하여 풀어보았다. DP를 활용한 풀이도 생각할 수 있는 문제이지만, DP를 활용할 경우 O(NK)의 시간복잡도로 시간초과가 나와 그리디를 활용해야만 하는 문제였다. 그리디 알고리즘 문제의 풀이 흐름에 따라 풀어보았다.

1. 직관적으로 높은 금액의 동전을 최대한 많이 사용할 수록 동전 갯수가 적어질 거라고 생각했다.
2. 위 생각을 증명해보았다.
   • 간단하게 하기 위해 동전의 가치가 10, 50, 100, 500원 뿐이라고 한다.
   • '동전을 최소로 소모하여 값을 지불하기 위해서는 500원은 최대한, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보자.
   • 증명을 편히 하기 위해 먼저 '동전을 최소로 소모하여 값을 지불할 때, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보겠다. 귀류법으로 생각하여 10/100원 동전을 5개 이상, 50원 동전을 2개 이상 사용하여 최소로 동전을 소모할 수 있다고 가정해보자. 10/100원이 5개 이상, 50원이 2개 이상이면 각각 50/500원, 100원으로 대체하여 동전의 갯수를 줄일 수 있으므로 가정이 모순된다. 그러므로 100원 4개 이하, 50원 1개 이하, 10원 4개 이하로 사용해야하는 것은 참이다.
   • 이제 500원을 최대한 사용해야한다는 것을 증명해야하는데 앞서 증명한 '동전을 최소로 소모하여 값을 지불할 때, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 이용하면 쉽게 증명된다. 귀류법으로 생각하여, 500원을 최소한으로 사용하여 동전을 최소로 소모하여 값을 지불할 수 있다고 가정해보자. 앞에서 증명한 내용에 따라 10/50/100원으로 지불할 수 있는 돈은 490원이 최대이다. 500원을 사용하지 않을 경우 10/50/100원으로 500원 이상을 지불해야하므로 가정이 모순되므로 500원을 최대한으로 사용해야하는 것은 참이다.
   • 문제의 조건에 따라 동전의 가치가 배수 관계이므로 언제나 성립한다.
3. 구현한다.

#include <iostream>
using namespace std;

int N;  
int K;  
int A[10];

int main(void)  
{  
ios_base::sync_with_stdio(0);  
cin.tie(0);

int ans = 0;
cin >> N >> K;
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = N - 1; i >= 0; i--)
{
    ans += K / A[i];
    K %= A[i];
}

cout << ans;

return 0;
}