[백준 *Java] - 제곱수의 합 (1699)

 

제곱수의 합 문제 보기

1699번: 제곱수의 합

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

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

입력
첫째 줄에 자연수 N이 주어진다.(1<= N <= 100,000)

출력
주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

이 문제를 풀 때, DP라는 문제라는 걸 알고있어서 DP문제 풀듯 먼저 사고를 할 거 같습니다.

그래서 일단 DP가 아닐 경우를 생각을해서 어떻게 풀까? 라는 고민을 먼저 했습니다.

 

for 문을 돌되, 예시로 11이라는 숫자로 생각해보면

11을 루트를 씌웁니다. 그러면 3.3166247903554 이러한 수가 나오는데,

결국은 최대 제곱수가 3일 것입니다.

그럼 하나 씩 -를 해주는 것입니다.

3 * 3 = 9

11 - 9 = 2

2를 (3-1) = 2*2 비교

2와 4를 비교하면 4가 더크니 2의 제곱수는 불가능

1를 (3-2) = 1*1  비교

2와 1를 비교하면 2가 더크니 1의 제곱수 가능

2 - 1 = 1

위와 동일하게 다시 재반복

하면, 3의 제곱 + 1의제곱 + 1의 제곱이 이 나오니 총 3항이 됩니다.

여러 테스트케이스를 고려해보고 이 상태로 코드를 구현합니다.

 

실패 코드라고 나오네요.. 일단 로직은 맞고 테스트케이스도 다 맞지만, 놓치고 있는 부분이 있는 듯합니다.

반례 찾기가 더 오래걸리겠네요..하

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

public class Main {

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

        int sqrtN = (int)Math.sqrt(N);

        StringBuilder sb = new StringBuilder();
        int i = sqrtN;
        while (N != 0) {
            if (N - (i*i) >= 0) {
                N = N - (i*i);
                sb.append(i);
                if(i == 1 && N != 0) i = 1;
                else i--;
            }else {
                if (N != 0) {
                    i--;
                }
            }
        }
        System.out.println(sb.length());
    }
}

 

여기서 다시 생각 전환으로 DP 풀듯 이 문제를 접근을 해보도록 하겠습니다.

DP 테이블에 어떤 수를 담을 지? 고민을 해보자. 부분문제를 이용하여 큰 문제를 해결하자 !

 

1 => 1²  DP[1] = (1항)

2 => 1² + 1²  DP[2] = DP[2-1] + 1; 기본값 (2항)   

3 => 1² + 1² + 1² DP[3] = DP[3-1] + 1 기본값 (3항) 

4 => 2²  DP[4] = DP[4-1] +1 기본값 (4항) => DP[4] = 4일 일경우? DP[4] = 1  (2² (1항))

5 => 2² + 1²  DP[5] = DP[5-1] + 1 (2항)=>  

6 => 2² + 1² + 1²  DP[6] = DP[6-1] + 1 (3항)

7 => 2² + 1² + 1² + 1² DP[7] = DP[7-1] + 1 (4항)

8 => 2² + 2² DP[8] = DP[8-1] + 1 (5항) => DP[8] =  2 (2항)  => DP[8] = DP[8/2] * 2 = 2 (2항)

9 => 3²

10 => 3² + 1

11 => 3² + 1² + 1² / 2² + 2² + 1² + 1² + 1² =>  DP[5] + DP[7] 

12 => 3² + 1² + 1² + 1²

13 => 3² + 2²

14 => 3² + 2² + 1²

15 => 3² + 2² + 1² + 1²

16 => 4²

8개......

25 => 5²

10개......

36 = 6²

 

---

결국 다른 분 코드를 보고 점화식을 어떻게 만드는 지 보았습니다.

제가 생각했던 건, Math.min 값을 이용해서 무조건 기본값 3 은 1이 3개, 10은 1이 10개 이런 식으로 만들어 준 뒤, 비교하는 식의 점화식을 만드려 했지만, 짜기 힘들었지만, 코드를 읽자마자, 놓치고 있던 부분을 알게 됐습니다.

제곱수니깐, 점화식에 제곱이랑 연관있다고 생각을해보고 그 쪽 부분으로 더 생각을 하고 점화식을 만들어봤어야 했는데 그러질 못했네요..

그리고 처음부터 점화식을 찾을 때 나열했던 항들이 최소항들만 써놓고 봤던 점이 실수였습니다.

문제에서도 여러 개의 제곱수의 합으로 나타낸다고 설명이 되어있으니, 여러 개의 제곱수의 합을 나열하고 생각을 했어야 했습니다...

 

성공한 코드입니다.

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] DP = new int[N+1];
        DP[1] = 1;
        for(int i = 2; i < N+1; i++) {
            DP[i] = i;
            for(int j = 1; j * j <= i; j++)
                DP[i] = Math.min(DP[i], DP[i - (j*j)] + 1);
        }

        System.out.println(DP[N]);
    }
}

위의 코드를 정리를 하면,

11 이라는 수 기준으로 설명을 하겠습니다.

DP[11] 이라는 수는 위에서 보면 3² + 1² + 1² / 2² + 2² + 1² + 1² + 1²   이렇게 두 가지 방법으로 11이라는 수를 만들 수 있습니다.

이건 3² + DP[2] 또는 2² + DP[7] 로 표현할 수 있습니다.

각 DP 갯수를 확인해보면서 위의 코드 로직을 돌려보면 충분히 이해하실 수 있으실 겁니다.