AtCoder蟻本 初級編 2-2 貪欲法 ①硬貨の問題

AOJ 0521 おつり

おつり | Aizu Online Judge

概要

1000円以下の買い物金額に対し、1000円支払ったとき
お釣りの硬貨の最小枚数を答えよ。

制約

問題のとおり。

方針

金額が大きい硬貨から使ってゆく。

解答

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int mo;
	cin >> mo;

	int res = 1000 - mo;

	int coins[6] = {500, 100, 50, 10, 5, 1};
	int ans = 0;

	rep(i, 6){
		int c = coins[i];
		int q = res / c;
		ans += q;
		res -= c * q;
	}

	cout << ans << endl;
}