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

문제 링크

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

나의 풀이

잘못된 접근

잘못 세운 점화식

$$ dp[i] = dp[i - (가장 큰 제곱근 ^ 2)] + 1$$ 

 

단순하게 가장 큰 제곱근의 제곱을 빼서 dp 테이블을 갱신하는 것이 최솟값이라고 생각을 했습니다.

 

예를 들어 i = 26의 경우

가장 큰 제곱근인 5의 제곱 25를 26에서 뺀 뒤 나온 1. 즉, dp[26-25] + 1 이 무조건 최솟값이라고 생각했습니다.

$$ 26 = 1^2 + 5^2$$

올바른 접근

점화식의 경우 위에서 세운 점화식이 아예 틀린 것은 아니지만 가장 큰 제곱근만 생각하는 것이 아닌 1 ~ 가장 큰 제곱근의 경우를 모두 생각해야 합니다. 12를 시도해보면 좋을 거 같습니다.

 

$$ dp[i] = min(dp[i - 1^2 부터  (가장 큰 제곱근^2)] + 1, dp[i])$$

위 점화식을 바탕으로 i=1부터 n까지 갱신을 하면 됩니다.

Code

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

public class Main {
    static int[] dp;

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

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

        for (int i = 1; i < n + 1; i++) {
            dp[i] = i;
        }

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

    }
}

Git

https://github.com/youngh0/java-algorithm/blob/master/algorithm/src/main/java/dp/boj_1699/Main.java