BOJ/1699) 제곱수의 합

제곱수의 합(1699), Silver3

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

문제풀이

Bottom-Up 방식을 이용한 DP를 활용하여 배열을 구성하였다.
일단 최대값은 1의 제곱으로만 구성된 경우이다. 따라서 자기 자신의 값인, dp[i] = i 로 초기화한다.
그리고 가장 작은 제곱수부터 가장 가까운 제곱수까지 루프를 돌면서 최소 개수를 찾는다.

예를 들어서 8을 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구해보자.

1 = 1^2
2 = 1^2 + 1^2
3 = 1^2 + 1^2 + 1^2
4 = 1^2 + 1^2 + 1^2 + 1^2 , 2^2
5 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2
6 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2 + 1^2
7 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2 + 1^2 + 1^2
8 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 2^2

위의 예시를 보면 8의 경우 8과 가장 가까운 제곱수인 4(2^2)를 8에서 뺀 4의 dp배열의 값을 활용했음을 알 수 있다.
식으로 표현하면 다음과 같은데, dp[8-4(2*2)] + 1 여기서 +1은 식에서 가까운 제곱수를 구하기 위해 빼준 값에 해당한다.
계속해서 값을 구하다보면 규칙을 찾을 수 있다.
자신의 제곱근까지의 값의 제곱수까지 탐색이 가능하고, 위의 식에 대입해가면서 가장 최소의 값을 찾으면 된다.

🤔 점화식

dp[i] = Math.min(dp[i], dp[i - j^2] + 1)

소스코드

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

        for(int i = 1; i <= n; 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]);
    }
}