제곱수의 합

제곱수의 합

 

문제

---

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

45 = 3^2 + 6^2

 

입력

---

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

출력

---

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

 

예제 입력

45

예제 출력

2

 

예제 입력

38

예제 출력

3

코드

///제곱수의 합 // greedy 하게 찾고 , 다시 찾기, 100점

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b[];
        int c[];
        int d[];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();

        int sqrt = (int)Math.sqrt(a);

        int tmpSqrt = sqrt;

        b = new int[(sqrt*sqrt)+1];

        int find = a;
        while (find > 0) {
            if(tmpSqrt*tmpSqrt <= find) {find -= tmpSqrt*tmpSqrt;  result++; b[tmpSqrt*tmpSqrt] = 1; }
            else tmpSqrt = tmpSqrt- 1;
        }

        findR(a,sqrt,0);

        System.out.println(result);

        sc.close();

    }

    public static void findR(int a, int sqrt, int c){
        if(a < 0 || c >= result || sqrt ==0 ) return;

        if(a==0) { result = c; return; }

        findR(a-(sqrt*sqrt),sqrt,c+1);
        findR(a-(sqrt*sqrt),sqrt-1,c+1);
        findR(a,sqrt-1,c);
    }

}

다이나믹 프로그래밍 (but 오히려 시간 초과 걸림)

//dynamic programming

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();

    //첫째 줄에 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int[] dp;

        a = sc.nextInt();
        dp = new int[a + 1];

        for (int i = 1; i * i <= a; i++) {
            dp[i * i] = 1;
        }

        for (int i = 1; i <= a; i++) {
            if (dp[i] == 1) ;
            else if (dp[i - 1] == 1) dp[i] = 2;
            else {
                dp[i] = dp[i - 1] + 1;
                for (int j = i - 1; j >= i/2; j--) {
                    if (dp[j] + dp[i - j] < dp[i]) dp[i] = dp[j] + dp[i - j];
                }
            }
        }

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


    }


}