5585번 거스름돈

그리디(탐욕) 알고리즘이다.

이 코드에서 주의할 점은

25번 째 줄 코드 >가 아니라, >=이다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int Coin[6] = { 500, 100, 50, 10, 5, 1 };
 
int money = 0;
 
int Search()
{
    int total = 1000 - money;
 
    int ret = 0;
 
    for (int i = 0; i < 6; i++)
    {
        while (total - Coin[i] >= 0)
        {
            total -= Coin[i];
 
            ++ret;
 
            if (total <= 0) break;
        }
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d", &money);
 
    printf("%d\n", Search());
    
    return 0;
}