← Natrag na lekciju 28 · Pohlepni algoritmi (greedy)

Kovanice

Lekcija 28 · Python vrijeme: 1,0 s memorija: 256 MB

Prodavač vraća ostatak kovanicama eura: 200, 100, 50, 20, 10, 5, 2 i 1 cent. Koliko najmanje kovanica treba za zadani iznos?

Ulaz

Jedan cijeli broj, iznos u centima.

Izlaz

Najmanji broj kovanica.

Ograničenja

1 ≤ iznos ≤ 1 000 000

Primjer 1

Ulaz
87
Izlaz
5

Primjer 2

Ulaz
400
Izlaz
2

Zapeo si?

Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.

Rješenje

Za predaju rješenja se prijavi.