최소개수 제곱수의 합 1 > 문제은행



문제은행

3290 : 최소개수 제곱수의 합 1

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 8 회    시도횟수: 17 회   



임의의 자연수는 제곱수의 합으로 나타낼 수 있다.

예를 들어 4 = 22, 5 = 22 + 12, 13 = 22 + 32 등 이다.

13   22 +  22 +  22 + 12으로도 나타낼 수 있지만  13 = 22 + 32 로 나타낼 때,

가장 적은 개수의 제곱수를 사용한다.

 

정수 N을 가능한 적은 개수의 제곱수의 합으로 나타내고자 한다.

이때 사용된 제곱수의 최소 개수를 출력하는 프로그램을 작성하시오.

 

 




첫 행에 테스트 케이스의 수 T가 입력된다. (1 <= T <= 1000)
다음 T개의 행에 Ni이 입력된다. (1 <= Ni <= 1,000,000)



각 테스트 케이스에 대하여 사용된 제곱수의 최소 개수를 행으로 구분하여 출력한다.


5
1
2
3
4
5
1
2
3
1
2


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.