Solução Informática - Nível Iniciante - Semana 21

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:

  1. 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)
  2. 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:


#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
}