[이러닝] 제곱수의합

스터디/알고리즘 문제풀이

JK- 2019. 1. 20. 15:17

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

45 = 3^2 + 6^2

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

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

문제풀이