ABC208 B問題 Factorial Yen Coin を貪欲に解く

ABC208 B問題を貪欲法で解いた解説です。

問題

atcoder.jp

高橋王国では 1! 円硬貨 ,2! 円硬貨 ,…,10! 円硬貨が流通しています。ここで、
N!=1×2×⋯×N です。

高橋君は全ての種類の硬貨を
100 枚ずつ持っており、P 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。
問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。

最小で何枚の硬貨を使えば支払うことができますか？

難しいポイント

最小の枚数をどうやって求めるのか、求め方に迷うかもしれません

解き方の方針

Pが最大でもなので、使える貨幣は最大でもです。
貪欲法の考え方で、大きい貨幣から順番に、貨幣の値を下回るまで使い、最後のまで繰り返します。

実装

P = int(input())
fact_list = [1] * 12
# 再帰メモ化で11!まで階乗の値を保存する
for i in range(1, 12):
    fact_list[i] = fact_list[i - 1] * i
j = 10
ans = 0
while P != 0:
    if P >= fact_list[j]:
        P -= fact_list[j]
        ans += 1
    else:
        j -= 1

print(ans)