[易趣]グリディ-お金を探して

🔔 質問する

あなたはレストランの会計を手伝っている人です.カウンターにはお釣りに使える500元、100元、50元、10元硬貨が無限に存在します.お客様に渡すお金がN元の時に探すコインの最低個数です.しかし、探すお金はいつも10の倍数です.

時間の複雑さ

作成されたコードから、通貨の種類のように繰り返し実行されることがわかります.通貨の種類がK個の場合、以下のソースコードの時間的複雑度はO(K)である.ちなみに、時間の複雑さからお探しのお金Nが見つからないことがわかります.すなわち,このアルゴリズムの時間的複雑さはコインの全種類の影響のみを受け,取り戻さなければならない金額の大きさとは無関係である.

🎯 解答方法

この問題はGRADYアルゴリズムで解くことができる代表的な問題であり,簡単な考えさえあれば問題を解決することができる.それは「最大の通貨単位から」おつりです.N元を探す時、最初に500元を見つけることができます.それから100元、50元、10元の硬貨を順番に探し出して、最小の硬貨の個数はすべて探し出すことができます.

💡 考えなければならないこと

すべてのアルゴリズム問題がGRADYアルゴリズムを使用できるわけではない.ほとんどの問題は,グリディアルゴリズムを用いた場合に「最適解」が見つからない可能性が高い.しかし、お金を探す問題では、「最大の通貨単位から」お金を探すように、貪欲に問題に近づくと、正しい答えを見つける保障がある場合、非常に効果的で直感的です.
グリディアルゴリズムで問題の解法を見つけるときは,その正しさを研究すべきである.GRADYアルゴリズムでお金を探す問題を解決できるのは、持っているコインの中で、大きい単位はいつも小さい単位倍数なので、小さい単位コインを総合して他の年を出すことはできません.例えば、800元を探す必要がありますが、通貨単位が500元、400元、100元の場合は考えてみましょう.この場合、グリディアルゴリズムは4枚の硬貨(500元+100元+100元+100元+100元)を取り戻す必要があり、最適な年は2枚の硬貨(400元+400元)を取り戻すことです.つまり、この問題では、大単位は小単位の倍数形式であるため、「最大単位の通貨から最小単位の通貨まで、順次確認し、遡及操作を行うだけ」という考え方が正当である.多くのGRADYアルゴリズム問題では,問題を解決するための最低限の考え方を考え,それが正当であるかどうかを検討してこそ,答えが得られる.

💻 Pythonコード

n = int(input())

coin_type = [500, 100, 50, 10]
answer = 0

for coin in coin_type:
    answer += n // coin # 최대한 거슬러 줄 수 있는 만큼
    n %= coin

print(answer)