백준(BOJ) 14916 거스름돈 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/14916

14916번: 거스름돈

문제 풀이에 이용된 알고리즘: 단순 구현

 

거스름돈으로 주는 동전의 개수를 최소화하고 싶다면, 우선 5원짜리 동전을 최대한 많이 사용하고 남은 금액을 2원으로 만들면 된다.

 

따라서 for문을 이용해서, 지급 가능한 5원짜리 동전을 하나씩 줄여가며, 매 경우에 5원으로 지급하고 남은 금액을 2원으로 지급 가능하다면 그 경우가 답이다.

 

/* BOJ 14916 거스름돈 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int mon;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> mon;
 
    for (int i = mon / 5; i >= 0; --i)
    {
        if ((mon - i * 5) % 2 == 0)
        {
            cout << i + (mon - i * 5) / 2 << endl;
            return 0;
        }
    }
 
    cout << -1 << endl;
 
    return 0;
}