【AtCoder版！蟻本】AOJ 0521 Change【貪欲法】

AtCoder版！蟻本の貪欲法の例題としてあげられているAOJ 0521 ChangeをPythonで解いていきます。

リンク

AOJ 0521

0521 - Change

問題文

太郎君はよくJOI雑貨店で買い物をする．
JOI雑貨店には硬貨は500円，100円，50円，10円，5円，1円が十分な数だけあり，いつも最も枚数が少なくなるようなおつりの支払い方をする．
太郎君がJOI雑貨店で買い物をしてレジで1000円札を1枚出した時，もらうおつりに含まれる硬貨の枚数を求めるプログラムを作成せよ．

制約

・入力は複数のデータセットからなる．各データセットは1行からなり，太郎君が支払う金額（1以上1000未満の整数）が1つだけ書かれている．入力データはゼロ１つの行で終了する．
・データセットの数は 5 を超えない．

解答例

while True:
    n = int(input())
    if n == 0:
        break

    tmp = 1000 - n
    coin = [500, 100, 50, 10, 5, 1]
    res = 0
    for i in range(6):
        if tmp == 0:
            break
        res += tmp // coin[i]
        tmp = tmp % coin[i]
    print(res)

解説

1～999円の買い物をして1000円札で支払いをしたときの、最も少ないおつりの枚数を答える問題です。

tmp変数におつりの金額を代入します。
coin配列には大きい順に硬貨の金額を格納していきました。

そのあとのfor文でおつりの枚数を求めていきます。
おつり金額tmpを500円硬貨の金額で割って500円硬貨を払う枚数をres変数に足しました。
tmp変数は500円を払い終えた後に残る金額に更新します。
この処理を100円、50円、…、1円と続けていきました。

ループを抜けた後におつりの枚数であるres変数を出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク