[白俊]5585:おつり

金をさがす

質問する

コード#コード#

#5585 : 거스름돈

money = 1000
price = int(input())
count = 0
array = [500, 100, 50, 10, 5, 1]

num = money - price


for coin in array:
  count += num //coin   # 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
  num %= coin

print(count)

に答える

持参した硬貨のうち、大きい単位は常に小さい単位の倍数であるため、小さい単位の硬貨を総合して他の年を生み出すことはできない.したがって,グリディアルゴリズムにより,単純に最大の通貨から探すことで最適解を見つけることができる.