[백준/C,C++] 5585번: 거스름돈

www.acmicpc.net/problem/5585

5585번: 거스름돈

풀이

그리디 알고리즘 문제 중에서 가장 기초적인 문제입니다.

 

현재 받을 수 있는 화폐의 종류 중 값이 큰 것부터 잔돈에서 빼주면 됩니다.

 

#include<iostream>

using namespace std;

int main(void)
{
    int n; cin >> n;
    n = 1000 - n;
    int changes[6] = { 500, 100, 50, 10, 5, 1 };
    int res = 0;

    for (int i = 0; i < 6; i++) {
        int tmp = n / changes[i];
        n -= (tmp * changes[i]);
        res += tmp;
        if (n == 0) break;
    }

    cout << res;

    return 0;
}

반례

Input

10

Output

10

 

Input

520

Output

8

 

Input

1000

Output

0