貪欲法の基本
- その時点で最善の手を尽くす
- 尽くした結果を目的とする値に反映させる。
- 次善の手になるようにする。
- 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]