Cantidad mínima de cuadrados perfectos
Dado un número entero n, se te pide encontrar la menor cantidad posible de cuadrados perfectos (1, 4, 9, 16, 25, 36, etc.) que sumen exactamente n. ¿Cuántos cuadrados perfectos utilizarías?
Entrada
La entrada contiene un único número entero n (1 ≤ n ≤ 60000).
Salida
El programa debe imprimir la cantidad mínima de cuadrados perfectos que se usarían.
Ejemplos
Entrada | Salida |
|---|---|
344 | 3 |
Explicación
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB