最小金種の支払いアルゴリズム

背景

• お釣りができないように払うという問題の場合

atcoder.jp

考え方

1. 支払い金額 / 一番大きい金種 = 払った金種の枚数
2. 支払い金額 % 払った金種 = 残りの支払い金額
3. 1-2を繰り返し
4. 払った金種の枚数の合計 = 最小金種支払い

例

2021円を払う.
1. 2021 / 1000 = 2.
2. 2021 % 1000 = 21.
3. 21 / 10 = 2.
4. 21 % 10 = 1.
5. 1 / 1 = 1.
6. 2 + 2 + 1 = 5

サンプル

import math
p = int(input())
bills = []
for i in range(1, 10+1):
    bills.append(math.factorial(i))
bills.reverse()

numOfBills = 0
for bill in bills:
    numOfBills += p // bill
    p %= bill
print(numOfBills)

• 見直したらなんでこれ階乗してんの？ってなったけど、問題で出現する使用可能な通貨が階乗の値だったということでしたw