[BOJ 5585, C++] 거스름돈

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

 

풀이

언제나 거스름돈의 개수가 가장 적게 줘야하므로 가장 큰 단위부터 내림차순으로 거스름돈을 주면 된다.

거스름돈의 개수는 몫으로 거스름돈을 뺀 나머지는 나머지로 구할 수 있다.

 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, ans = 0, cost[6] = { 500, 100, 50, 10, 5, 1 };
 
    cin >> n;
    n = 1000 - n;
 
    for (auto nx : cost) {
        ans += n / nx;
        n %= nx;
    }
 
    cout << ans << endl;
}