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:
https://gist.github.com/anitainfo/c4c452aa5a7b4bb8e8412968b1c7e3ea