Question

У Ричарда в банке есть n долларов. Он хочет снять всю сумму наличными. Номиналы купюр равны 1, 5, 10, 20, 100. Какое минимальное число купюр должен получить Ричард после того, как снимет все деньги? На вход программе поступает одно положительные целое число n.
ДАЮ 60 БАЛЛОВ
на языке программирования python

Answer 1

Python:

N = int(input())  # сумма, которую нужно выдать

nominal = [100, 20, 10, 5, 1]  # номиналы банкнот

F = [0]

for m in range(1, N + 1):

   F.insert(m, float("+inf"))

   for i in range(len(nominal)):

       if m >= nominal[i] and F[m - nominal[i]] + 1 < F[m]:

           F[m] = F[m - nominal[i]] + 1

print(F[N])