기억을 지배하는 자

문제

숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.

45 = 3^2 + 6^2

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

필요한 제곱 수의 최소 개수를 출력한다.

예제 입력

45

예제 출력

2

예제 입력

38

예제 출력

3

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution07.java