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

문제

14916번: 거스름돈

풀이

그리디

 

n이 5로 나누어 떨어진다면 5원으로 거스름돈을 채울 수 있다. 5로 나누어 떨어지지 않는다면 2원과 같이 채워야 한다. 1원이 아니라 2원이기 때문에, 5로 나눈 나머지를 2원으로 맞춰서 낼 수 없다. 예를 들어 1원 혹은 3원이 남았다면 2원으로 채울 수 없다. 

n이 5로 나누어 떨어지지 않는다면, n이 5로 나누어 떨어지거나 n이 0 이하가 될 때까지 2씩 차감한다. n이 0미만이 된다면, 거슬러 줄 수 없는 경우이다.

코드

#include <iostream>

using namespace std;

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

    int n;
    cin >> n;

    // 5원으로 모두 줄 수 있는 경우
    if (n % 5 == 0)
    {
        cout << n / 5;
    }
    else
    {
        // 5원으로 줄 수 없는 경우
        int answer = 0;
        while (n > 0)
        {
            // 5로 나누어떨어질 때까지 2 차감
            answer++;
            n -= 2;

            if (n % 5 == 0)
            {
                answer += n / 5;
                cout << answer;
                break;
            }
        }
    }

    // 1이나 3처럼 거슬러 줄 수 없는 경우
    if (n < 0)
    {
        cout << "-1";
    }

    return 0;
}