LT07-Editorial

editorial
, , , ,
1

Problem Link

Loop Through

Author:pskalbhav1

Difficulty

EASY

Prerequisites

Greedy

Problem Statement

Jack likes buying "Retro Art" images. Once, during a party, he was given a challenge. Given n dollars cheque, he has to exchange it with cash of denominations 1, 5, 10, 20, 100 to buy a very famous Retro art. What is the minimum number of bills he could receive after withdrawing his entire balance?

Jack really wants the Retro Art. So help him to solve the challenge and the painting.

Approach


The problem is to minimize x1+x2+x3+x4+x5 given that x1+5x2+10x3+20x4+100x5 = n.
It is pretty simple to see that we can operate greedily: take as many 100 as we can, then 20, then 10, etc.

The solutions works because each number in the sequence 1,5,10,20,100 is a divisor of the number after it.

Solution

 #include <bits/stdc++.h>
 using namespace std;
 int n;
 main()
{
   cin>>n;
   cout <<n/100+n%100/20+n%20/10+n%10/5+n%5;
}