문제 숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다. 45 = 3^2 + 6^2 입력 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 출력 필요한 제곱 수의 최소 개수를 출력한다. 예제 입력 45 예제 출력 2 예제 입력 38 # 풀이 우선 문제의 규칙은 이렇다 dp[0] = 0 dp[1] = 1^1 dp[2] = 1^1 + 1^1 dp[3] = 1^1 + 1^1 + 1^1 dp[4] = 1^1 + 1^1 + 1^1 + 1^1 or 2^2 … dp[7] = 2^2 + 1^1 + 1^1 + 1^1 dp[..