Solução por Anita Ramos
Para esse problema, utilizaremos a seguinte ideia: analisamos a quantidade de moedas de valor $$X$$ que “cabem” em $$N$$, em ordem decrescente de valor em dinheiros, sempre subtraindo o valor da soma dessa quantidade de moeda do valor total do troco, por exemplo, para $$N=106$$, temos:
- 100 dinheiros: máximo de 1 moeda -> $$N=106-100=6$$
- 50 dinheiros: máximo de 0 moedas -> $$N=6-0=6$$
- 25 dinheiros: máximo de 0 moedas -> $$N=6-0=6$$
- 10 dinheiros: máximo de 0 moedas -> $$N=6-0=6$$
- 5 dinheiros: máximo de 1 moeda -> $$N=6-5=1$$
- 1 dinheiros: máximo de 1 moeda -> $$N=1-1=0$$
Para chegar ao resultado final mínimo de quantas moedas representarão o troco, basta somar os valores de moedas utilizadas, ou seja, o número de moedas que seja $$< 0$$.
Em código, faremos o cálculo para cada valor em dinheiros de cada moeda em ordem decrescente, que será da seguinte forma:
- $$cont+=n/valor$$, em que soma-se a $$cont$$ o resultado da divisão de $$n$$ pelo valor a ser analisado, lembrando que $$valor*cont \leq n$$ sempre por se tratar do resultado de uma divisão guardada em um inteiro ($$int$$)
- $$n-=valor*(n/valor)$$, em que subtrai-se o maior preço que esse mesmo valor de moeda consegue pagar do troco que ainda falta, ou seja, subtrai-se apenas o número somado no item “1.” vezes o valor dessa moeda
Segue o código comentado para melhor compreensão da solução:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> //biblioteca utilizada | |
| using namespace std; | |
| int main() { | |
| int n, cont=0; //declaração de variáveis | |
| scanf("%d", &n); //leitura do 'n' | |
| cont+=n/100; //soma o número de moedas 100 que cabem em n | |
| n-=100*(n/100); //subtrai o valor de moedas 100 que já serão do troco | |
| cont+=n/50; //soma o número de moedas 50 que cabem em n | |
| n-=50*(n/50); //subtrai o valor de moedas 50 que já serão do troco | |
| cont+=n/25; //soma o número de moedas 25 que cabem em n | |
| n-=25*(n/25); //subtrai o valor de moedas 25 que já serão do troco | |
| cont+=n/10; //soma o número de moedas 10 que cabem em n | |
| n-=10*(n/10); //subtrai o valor de moedas 10 que já serão do troco | |
| cont+=n/5; //soma o número de moedas 5 que cabem em n | |
| n-=5*(n/5); //subtrai o valor de moedas 5 que já serão do troco | |
| cont+=n; //soma o número de moedas 1 que cabem em n | |
| printf("%d", cont); //imprime o número de moedas | |
| return 0; //retorna a 0 | |
| } |