BOJ 1699) 제곱수의 합

문제

 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

 

전개

sol.

 처음에는 자연수를 큰 수의 제곱부터 더 이상 더할 수 없을때까지 더하면 되겠다고 생각함

재귀함수꼴로 더하는 개수를 count해준 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main practice = new Main();
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        int cnt=0;
        System.out.print(practice.getMinSquareSum(input, cnt));
    }

    private int getMinSquareSum(int input, int cnt) {
        int n=0;
        while(input>=(n+1)*(n+1))
            n++;
        if(input==0)
            return cnt;
        return getMinSquareSum(input-n*n, cnt+1);
    }
}

그런데 생각해보니까 제일 큰 수의 제곱이 꼭 더해지지는 않는다는것을 깨달음.

ex)98=49+49. 81+16+1하면 cnt가 3이된다.

 

sol2.

 그렇다면 n의 가장 작은 제곱수의 합을 구하려면 더해지는 제곱수에 순서나 규칙이 없다는 이야기이므로, 1~n-1까지의 수가 들어갈지 말지 여부는 끝까지 결과를 보지 않고는 결정할 수 없다는 말이다.

이러한 경우 모든 경우를 특정한 식을 구하지 않고 브루트 포스로 풀 경우 수행시간이 매우 커질 수 있다는 생각이 들었다.

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main practice = new Main();
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        int n=0;
        int best=999;
        while((n+1)*(n+1)<=input)
            n++;


        while(n>0) {
            int rst = practice.getMinSquareSum(input, 0, n);
            if(rst < best)
                best = rst;
            n--;
        }
        System.out.println(best);
    }


    private int getMinSquareSum(int input, int cnt, int n) {
        int k=0;
        while(input>=(k+1)*(k+1) && n>=k)
            k++;
        if(input==0)
            return cnt;
        else {
            if(input-k*k>=0)
                return getMinSquareSum(input-k*k, cnt+1, n);
            else
                return 1000;
        }
    }
}

n의 한계치를 바꾸어가면서 모든 경우를 조사하는 방법이다.

60000정도를 넘어가면 stack overflow가 발생하는데, 아마 너무 많은 연산을 필요로 해서 발생하는 것 같다

 

 

sol3.

문제는 이 문제의 풀이를 위해서는 NP와 같이 branch중에 한 가지의 풀이방법을 제시하면 되는것이 아니라,

모든 branch중에서 best case를 찾아야 한다는데 있다.

규칙이 없다면 무조건 전체 branch를 탐색해야 한다는 말이고, 여기서 branch and bound의 방법으로 유망하지 않은 branch를 잘라내는 방식으로 풀어보자.

sum of subset문제와 같이 branch가 고정되지 않았다. 단순히 포함된다/되지않는다의 문제가 아니다 (중복이 이루어 질 수 있다)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main practice = new Main();
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        int[] c = new int[100001];
        for(int i=1; i<=100000; i++) {
            c[i]=i;
        }
        for(int i=1; i<=100000; i++) {
            for(int j=1; j*j<=i; j++) {
                if(c[i]>c[i-j*j]+1)
                    c[i]=(c[i-j*j]+1);
            }
        }
        System.out.println(c[input]);
    }

}

input이 17일때를 생각해보면, 17은 1,4,9,16의 합으로만 구성된다. 따라서 16+1, 13+4, 8+9, 1+16의 꼴로만 구성되었을 것이다. 여기서 DP를 사용할 수 있다는 것을 알 수 있다.

배열 c[i]가 input이 i일때 i의 최소 제곱수라고 하면, c[17]=min(c[16]+c[1], c[13]+c[4], c[8]+c[9], c[1]+c[16])과 같은 식을 세울 수 있다.

     for(int i=1; i<=100000; i++) {
         for(int j=1; j*j<=i; j++) {
             if(c[i]>c[i-j*j]+1)
                 c[i]=(c[i-j*j]+1);
         }
      }

 

정리

아직 알고리즘 정리가 완벽하게 되지않은상태에서 종강하자마자 꽂혀서 푼 문제.. 완벽하게 정리먼저 끝내야겠다.