Solução de Pedro Michael, comentários de Rogério Júnior
Para ver o problema original, clique aqui.
Este problema se torna muito fácil pelo seguinte motivo: Seja 
o valor que queremos alcançar somando fatoriais, então podemos usar uma estratégia gulosa colocar o maior fatorial que não supera 
, pois ele é múltiplo de todos os fatoriais menores (definição de fatorial).
Deste modo, basta sempre usarmos o maior fatorial que pudermos, e teremos nossa resposta ótima. Segue o código para melhor entendimento.
This file contains 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 <stdio.h> | |
| int main() | |
| { | |
| int fat[10], n, j, cont = 0; | |
| fat[0] = 1; | |
| // calculo todos os fatoriais necessários | |
| for(int i = 1; i <= 9; i++) | |
| fat[i] = i*fat[i-1]; | |
| // leio o valor de n | |
| scanf("%d", &n); | |
| //enquanto n!=0 | |
| while(n) | |
| { | |
| // procuro o maior fatorial que cabe em n | |
| j = 1; | |
| while(n >= fat[j]) | |
| j++; | |
| // subtraio o seu valor de n | |
| n-=fat[j-1]; | |
| // e o adiciono na contagemd a resposta | |
| cont++; | |
| } | |
| // por fim, basta imprimir o valor de cont | |
| printf("%d\n", cont); | |
| return 0; | |
| } |