[백준 14916번] 거스름돈

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

14916번: 거스름돈

<문제 풀이> 그리디 알고리즘

 

숫자가 큰 동전은 최대한으로 사용하고 숫자가 작은 동전은 최소한으로 사용하는 것이 최적의 해가 됩니다.

 

N이 5로 나누어 떨어질 때까지 N에서 2를 한 번씩 빼보는 것을 반복하면 됩니다.

 

N이 5로 나누어 떨어지면 그 몫은 5원 동전의 총 개수

N에서 2를 한 번 빼면 2원 동전 하나 사용

 

 

 

 

<C++소스코드>

#include<iostream>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
 
    int n;
    int ans = 0;
    cin >> n;
    while (n > 0) {
        if (n % 5 == 0) {
            ans += n / 5;
            n /= 5;
            break;
        }
        else {
            n -= 2;
            ans++;
        }
    }
    if (n < 0)cout << -1;
    else cout << ans;
    return 0;
}