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

문제

5585번: 거스름돈

풀이

그리디

 

기본적인 그리디 알고리즘 문제. 큰 동전부터 거스름돈을 최대한 처리한다.

코드

#include <iostream>

using namespace std;


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

    int N;
    cin >> N;

    int change = 1000 - N;

    int coins[6] = { 500, 100, 50, 10, 5, 1 };
    int current = 0;

    int answer = 0;

    // 큰 동전부터 시작하여, 최대한 거슬러 줄 수 있을 때까지 준다.
    while (current < 6)
    {
        while (change - coins[current] >= 0)
        {
            change -= coins[current];
            answer++;
        }
        current++;
    }

    cout << answer;

    return 0;
}