Algoogle

Algorithm for Programming Contest

AOJ 0521 Change

Category: AOJ Tag: greedy

Change

問題概要


解法


greedyにやるだけ

コード


(0521.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define rep(i, b) for(int i = 0; i < b; i++)
using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        n = 1000 - n;
        int ans = 0;
        int c[6] = {500,100,50,10,5,1};
        rep(i,6){
            while(n/c[i]){
                ans++;
                n -= c[i];
            }
        }
        cout << ans << endl;
    }
}

Comments