AtCoder ABC 208 B – Factorial Yen Coin Python解説

スポンサーリンク

Factorial Yen Coin

高橋王国では 1! 円硬貨 ,2! 円硬貨 ,…,10! 円硬貨が流通しています。ここで、N!=1×2×⋯×N です。高橋君は全ての種類の硬貨を 100 枚ずつ持っており、P 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。
問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。
最小で何枚の硬貨を使えば支払うことができますか?

AtCoder Beginner Contest「Factorial Yen Coin」

P円を硬貨で支払うときの最少枚数を答えます。直観でわかるように、使える硬貨のうち、金額の大きい硬貨から順に使っていけば最小枚数になります。

p = int(input())

a = []
tmp = 1

for i in range(1, 11):
    tmp *= i
    a.append(tmp)
    
ans = 0

for i in reversed(range(10)):
    ans += p // a[i]
    p %= a[i]
    
print(ans)

まず、配列aに使える硬貨を入れていきます。硬貨の金額は階乗になっているので、tmp *= i したものを入れます。そして、硬貨の金額が大きいものから使いたいので、reversed(range(10))とし、ansにP円を硬貨で割ったときの枚数を入れて完了です。

階乗を計算するにはPythonの組み込み関数のfactorialを使う方法もあります。

from math import factorial

p = int(input())

ans = 0

for i in reversed(range(1, 11)):
    ans += p // factorial(i)
    p %= factorial(i)
    
print(ans)

最初のコードと考え方は一緒ですが、factorialを使うと階乗を計算した配列を用意する必要がないので、P円を10!から順に割って枚数を計算しています。