10-7: 제곱수의 합

제곱수의 합

 

문제

---

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

45 = 3^2 + 6^2

 

입력

---

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

출력

---

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

 

예제 입력

45

예제 출력

2

 

예제 입력

38

예제 출력

3

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class dp_sum_squares {

    /**
     * 제곱수의 합
     *
     *
     * 문제
     * 숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.
     *
     * 45 = 3^2 + 6^2
     *
     * 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )
     * 출력:
     필요한 제곱 수의 최소 개수를 출력한다.
     *
     * 예제 입력:
     *
     * 45
     *
     *
     * 예제 출력:
     * 2
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int dp[] = new int[N+1];


        dp[1] = 1;
        dp[2] = 2;

        for (int i=3; i<N+1; i++){
            for (int j=1; j*j<=i; j++){
                if (dp[i]==0 || 1+dp[i-j*j] < dp[i]){
                    dp[i] = 1+ dp[i-j*j];
                }
            }
        }

        System.out.println(dp[N]);

    }
}