[AJ/DP] 제곱수의 합

문제

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

45 = 3^2 + 6^2

입력

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

출력

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

예제 입력

45

예제 출력

2

예제 입력

38

예제 출력

3

---

풀이

N	풀이	개수
1	1	1
2	1 + 1	2
3	1 + 1 + 1	3
4	2^2	1
5	2^2 + 1	2
6	2^2 + 1 + 1	3
7	2^2 + 1 + 1 + 1	4
8	2^2 + 2^2	2
...	...	...

N = 8 일 경우,

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1  -> 8개

2^2 + 1 + 1 + 1 + 1  -> 5개

2^2 + 2^2 + 1 + 1  -> 4개

2^2 + 2^2 +2^2  -> 3개 

8보다 보다 작은 제곱수들 (1, 2^2) 을 사용하여 만들 수 있는 경우의 수 들 중

최소 개수를 math.min을 사용하여 구한다. 

코드

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int data[] = new int[n + 1];
        int nsqrt = (int) Math.sqrt(n);

        if (n == nsqrt * nsqrt)
            data[n] =1;
        else {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= (int) Math.sqrt(i); j++) {
                    if(i == j*j)
                        data[i] = 1;
                    else if(data[i]>0)
                        data[i] = Math.min(data[i], data[j*j] + data[i-j*j]);
                    else
                        data[i] = data[j*j] + data[i-j*j];
                }
            }
            
        }
        System.out.println(data[n]);

    }

}