お財布メタボ診断 [パソコン甲子園2014 予選 B]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0296?year=2014

考察過程

1. 合計丁度1000円が作れるかを判定すればいい
2. 簡単な判定方法を探す
3. 大きい硬貨をなるべく使って1000円に近い金額を作ろうとすればいいのでは？

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0296/judge/3156111/C++14

大きい硬貨をなるべく使って1000円に近い金額を作る貪欲をすればいい。
ピッタリ1000円が作れればお札に交換できる。
変数を配列にして実装するとスッキリ書ける。

int c[6], yen[6] = { 1,5,10,50,100,500 };
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 6) cin >> c[i];

    int sm = 0;
    rrep(i, 5, 0) if(sm < 1000) {
        int d = 1000 - sm;
        int use = min(c[i], d / yen[i]);
        sm += use * yen[i];
    }

    if (sm == 1000) cout << "1" << endl;
    else cout << "0" << endl;
}