Программирование на Python. Ведьмаку заплатите чеканной монетой
Всем известно, что ведьмак одолеть любых чудовищ, однако его услуги обойдутся недешево, к тому же ведьмак не принимает купюры, он принимает только чеканные монеты. В мире ведьмака существуют монеты с номиналами 1, \, 5, \, 10, \, 251,5,10,25.
Напишите программу, которая определяет какое минимальное количество чеканных монет нужно заплатить ведьмаку.
Формат входных данных
На вход программе подается одно натуральное число, цена за услугу ведьмака.
Формат выходных данных
Программа должна вывести минимально возможное количество чеканных монет для оплаты.
sm = int(input())
coins = [1, 5, 10, 25]
ls = [0] * (sm+1)
for i in range(1, sm+1):
ls[i] = float('inf')
for coin in coins:
if coin <= i:
ls[i] = min(ls[i], ls[i-coin]+1)
print(ls[-1])