제곱수의 합
면접 대비시간 제한2초메모리 제한128 MB
N이 100,000 이하일 때, 제곱수들의 합으로 N을 표현하는 데 필요한 최소 항의 개수를 구합니다.
문제
자연수 N은 N보다 작거나 같은 제곱수 몇 개의 합으로 나타낼 수 있다. 예를 들어 11은 3^2 + 1^2 + 1^2처럼 세 항으로 표현할 수 있고, 2^2 + 2^2 + 1^2 + 1^2 + 1^2처럼 다섯 항으로도 표현할 수 있다.
가능한 모든 표현 중에서 사용하는 제곱수 항의 개수가 가장 적은 값을 구하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 <= N <= 100,000)
출력
N을 제곱수들의 합으로 나타낼 때 필요한 제곱수 항의 최소 개수를 출력한다.