[백준 알고리즘, 자바] Q1699 제곱수의 합 - 동적계획법

1. Java 구현

 (1) 처음 구현 - 완전 실패 

            
import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        int start = (int) Math.sqrt(n);
        while(n > 0 && start > 0) {
            if(n >= Math.pow(start, 2)) {
                n -= Math.pow(start, 2);
                System.out.println(start + "~");
                cnt++;
            } else {
                start—;
            }
        }

        bw.write((cnt) + "\n");
        bw.close();
    }

}

 (2) 성공 - 시간복잡도 2500ms

          
import java.io.*;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];

        for (int i = 1; i < arr.length; i++) {
            arr[i] = isSquare(i) ? 1 : Integer.MAX_VALUE;

            if(arr[i] > 1)
                for (int j = 1; j <= (i / 2); j++)
                    arr[i] = Math.min(arr[i], arr[j] + arr[i - j]);
        }

        bw.write((arr[n]) + "\n");
        bw.close();
    }

    public static boolean isSquare(int num) {
        return Math.pow((int)Math.sqrt(num), 2) == num;
    }
}

 (3) 성공 - 시간복잡도 180ms 

          
import java.io.*;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];

        for (int i = 0; i < arr.length; i++)
            arr[i] = i;

        for (int i = 1; i < arr.length; i++)
            for (int j = 1; j * j <= i ; j++)
                arr[i] = Math.min(arr[i], arr[i - j * j] + 1);

        bw.write((arr[n]) + "\n");
        bw.close();
    }
}

2. 코드설명

 1번 방식은 시간복잡도를 떠나서 완전히 실패한 방식이었다. 1번 방식을 예를들어 설명해보겠다. 27을 입력받았을 때, 27보다 작은 제곱수를 계속해서 빼는 방식이다.

 27보다 작은 제곱수 25를 빼면 2가 되고, 2보다 작은 제곱수 1을 빼고, 또 1을 뺀다. 그렇다면 3이 답으로 나온다. 될거라 생각했지만 반례가 존재했다.

  반례 : 72 = 64 + 4 + 4 -> 72 = 36 + 36 으로 표현 가능

 2번 방식으로 바꾸었다. 2번 방식은 동적계획법을 활용했다. 이전에 답이 가장 최적이라고 가정하고 문제를 풀었다. 그리고 이전의 숫자의 값에 대한 최적값을 저장할 수 있는 

 배열을 생성했다. 이 배열에서 arr[27]은 27이 가질수 있는 최적의 제곱수의 갯수를 나타낸다. 그러면 2번도 예를들어 설명해보겠다. 

 27을 입력받았을 때, 27은 아래의 값중 최소값이다.

  arr[26] + arr[1], arr[25] + arr[2], arr[24] + arr[3] ..... arr[13] + arr[11], arr[12] + arr[12]

 27보다 작은 수에 대해서는 이미 각각이 최적의 값이기 때문에 여기서 최소값을 찾으면 된다. 하지만 이 경우에는 시간복잡도가 높아 문제는 풀 수 있지만 시간이 많이 소요된다.

 3번 방식이 2번 방식과 비슷한 접근이지만, 조금 더 고민을 해야 나올 수 있는 답이다. 나는 솔직히 단번에 3번까지 도달못하고, 2번까지 도달한 후에나 가능했다. 

 이번에도 27를 예로 들겠다. 27은 arr[27 - 1^2], arr[27 - 2^2], arr[27 - 3^3], arr[27 - 4^2], arr[27- 5^2] 의 값 중 최소값중 1을 더한수가 27의 최적의 답이다.

 왜냐면... 나는 내가 원하는 값 27에 재곱수를 빼주었다. 그리고 재곱수를 빼준 값은 이전에 최적의 값으로 산출했다. 결국은 arr[26], arr[23], arr[18], arr[11], arr[2] 의 값에서

 1을 더해야 하는데... 1을 더하는 이유는 재곱수 때문이다.

 설명이 좀 이상할 수 있다... 그럴수 밖에 없다... 지금 마라톤 뛰자마자 바로 문제를 풀고 포스팅하기 때문이다. 방금 까지는 다리만 아팠는데... 문제를 풀면서 머리도 아파졌다...

 한편으로 타자를 손으로 치는 거에 대해 감사한다. 발로 쳐야했다면 타자를 치지 못했을 것이다... 직립보행도 안된다... 인간이기를 포기하고 잠시만 4족보행 해야겠다....

3. Pain Point

 3번 방식을 생각하지를 못했다. 2번 방식에서 최고의 방식은 아니라고 생각을 해서 다른 답변을 확인하면서 알게되었다. 솔직히 시간을 더 줘도 생각했을까? 라는 생각이 든다.

 접근 방식은 좋았는데... 아쉬웠다...