[백준] 1699번. 제곱수의 합(JAVA)

문제

https://www.acmicpc.net/problem/1699

---

풀이(35분)

import java.io.*;

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[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 최악의 경우 (1^2 + 1^2 + ... + 1^2)
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        System.out.println(dp[n]);
    }
}

 

문제풀이 초반 아래와 같은 식을 사용하여 문제를 해결하려고 하였다. 12의 경우 4+4+4가 최적인데 9+1+1+1이 되는 문제가 있었다.

역시 어느정도는 본인이 먼저 예시를 생각해두고 풀이를 진행하는 것이 좋다고 느꼈다. 왜냐면 문제에 있는 기본 예제는 모두 통과하기 때문에 처음에 틀린지 모르고 문제를 제출했었다.

arr[n] = 1 + arr[(int)(n-Math.floor(sqrt)*Math.floor(sqrt))];

 

위의 최종 풀이를 보면 다음과 같다.

1. 기본적으로 n번째 수는 n만큼의 제곱수의 합으로 해결할 수 있다.(1+1+1...)

2. j = 1; j *j <= i; j++ 이라는 다소 생각하기 어려운 for문을 통해 진행된다.

2-1. 먼저 dp[n]과 dp[n-j*j*] 를 비교한다. 순서대로 살펴보자. dp[n-1] + 1, dp[n-4] + 1, dp[n -9] + 1 과 같이 비교되며 최솟값을 찾는 방식이다.

2-2. 그럼 제곱수는 어떻게 제대로 1이 들어가?? 라는 문제가 있는데. dp[0]은 배열을 선언할 때 기본으로 0으로 초기화된다. 그럼 for문을 통해 dp[n] = dp[n-n] + 1이라는 값이 저장되게 된다. 즉 dp[0] + 1으로 항상 1이 저장되는 것이 보장될 수 있다는 것이다!