おつり14916回

📜 理解问题

春香はコンビニのカウンターで働いています.
お客さんは2元と5元の小銭しかありません.2元の硬貨と5元の硬貨は無限に多い.コインの個数は最小限にしなければならない.おつりがnなら、最小コインの個数を教えてくれるプログラムを書いてください.
例えば、15元なら5元3個、14元なら5元2個、2元2個の計4個、13元なら5元1個と2元4個の計5個、硬貨の個数が一番少ない.

💡 問題の再定義

小銭を5元と2元で最も少ない硬貨を渡すときは、この硬貨の個数を印刷します.

▼▼▼計画作成

グリディアルゴリズムを使用すると、最小限のコインを選択できます.まず、5元が一番多く使われているのはコインが一番少ないので、まず5元を減らすことができるかどうかを考えます.この場合、以下の2点を考慮します.
1.今探しているお金は5元より大きいです.
2.今戻ってきた小銭から5元差し引いた金額は5元か2元に分けるべきです.
上記の手順が満たされた場合、5元を減算し、残りの金額で比較します.5元を減算できない場合は、上記の手順と2元を再比較し、2元を減算できない場合は-1を出力します.

💻 計画の実行

if __name__ == '__main__':
    n = int(input())
    cnt = 0
    while n > 0:
        if n >= 5 and ((n - 5) % 5 == 0 or (n - 5) % 2 == 0):
            n -= 5
            cnt += 1
        elif n >= 2 and ((n - 2) % 5 == 0 or (n - 2) % 2 == 0):
            n -= 2
            cnt += 1
        else:
            cnt = 0
            break
    if cnt:
        print(cnt)
    else:
        print(-1)

🤔 振り返る

これはグリディアルゴリズムで解決できる問題です.グリディアルゴリズムは、現在、上記の問題を解決するのに最も適したアルゴリズムである.