JOI 予選 2008 A - おつり (AOJ 0521) (5Q, 難易度 1)

今や超有名な Greedy 問題「コインの枚数最小化問題」

• 問題へのリンク

問題概要

JOI 雑貨店には硬貨は 500 円、100 円、50 円、10 円、5 円、1 円の硬貨が十分な枚数ある。

円の買い物をして 1000 円を支払った太郎くんに、硬貨の枚数が最小となるようにお釣りを渡すときの、効果の枚数を答えよ。

制約

• 

考えたこと

この問題は超有名だ。次のようにすればよい（日常生活からも違和感なくイメージできることだと思われる）。なお、お釣りの金額を （）とする。

---

• 円を超えない範囲で、 円で渡せるだけ渡す
• その剰余金額を超えない範囲で、 円で渡せるだけ渡す
• その剰余金額を超えない範囲で、 円で渡せるだけ渡す
• その剰余金額を超えない範囲で、 円で渡せるだけ渡す
• その剰余金額を超えない範囲で、 円で渡せるだけ渡す
• その剰余金額を超えない範囲で、 円で渡せるだけ渡す

---

あとは、この手続きを実装しよう。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int X, res = 0;
    cin >> X;
    int N = 1000 - X;

    vector<int> coins = {500, 100, 50, 10, 5, 1};
    for (auto coin : coins) {
        // 剰余金額 N 円を coin 円で渡せるだけ渡す
        res += N / coin;
        N %= coin;
    }
    cout << res << endl;
}