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