蟻本 P42 硬貨の問題

貪欲法の基本

1. その時点で最善の手を尽くす
2. 尽くした結果を目的とする値に反映させる。
3. 次善の手になるようにする。
4. 1に戻る

硬貨の問題

A=int(input())
*C,=map(int,input().split())
coin=[1,5,10,50,100,500]

ans=0

for i in range(5,-1,-1):
    t=min(A//coin[i],C[i])
    A-=t*coin[i]
    ans+=t
print(ans)

気を付けるところ

• 制限を考慮して、反映させる(minのところ)
• 切り捨て a//coin[i]