[JAVA] 백준 (실버3) 17626번 Four Squares

링크

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

---

문제 설명

정답률 43.705%

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, $26$은 $5^2$과 $1^2$의 합이다. 또한 $4^2 + 3^2 + 1^2$으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 $15663 = 125^2 + 6^2 + 1^2 + 1^2$라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: $11339 = 105^2 + 15^2 + 8^2 + 5^2.$

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

---

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

---

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

---

풀이

일단 규칙성을 찾기 위해 1부터 계산을 해본다.
$1 = 1^2$
$2 = 1^2 + 1^2$
$3 = 1^2 + 1^2 + 1^2$
$4 = 2^2$
$5 = 2^2 + 1^2$
$6 = 2^2 + 1^2 + 1^2$
$7 = 2^2 + 1^2 + 1^2 + 1^2$
$8 = 2^2 + 2^2$
$9 = 3^2$
$10 = 3^2 + 1^2$
$11 = 3^2 + 1^2 + 1^2$
$12 = 3^2 + 1^2 + 1^2 + 1^2$
$13 = 3^2 + 2^2$
$14 = 3^2 + 2^2 + 1^2$
$15 = 3^2 + 2^2 + 1^2 + 1^2$
$16 = 4^2$
규칙성을 보면 제곱이 되는 수는 당연히 제곱수가 1개가 되고 그 다음 제곱수가 될 때까지 이전 수의 제곱수들의 합을 순서대로 가져온다.

이를 점화식으로 제곱수의 개수로 나타내면 다음과 같다.
$dp[1] = 1$
$dp[2] = dp[1] + dp[1] = 2$
$dp[3] = dp[1] + dp[2] = 3$
$dp[4] = 1$
$dp[5] = dp[4] + dp[1] = 2$
$dp[6] = dp[4] + dp[2] = 3$
$dp[7] = dp[4] + dp[3] = 4$
$dp[8] = dp[4] + dp[4] = 2$
$dp[9] = 1$
$dp[10] = dp[9] + dp[1] = 2$
$dp[11] = dp[9] + dp[2] = 3$
$dp[12] = dp[9] + dp[3] = 4$
$dp[13] = dp[9] + dp[4] = 2$
$dp[14] = dp[9] + dp[5] = 3$
$dp[15] = dp[9] + dp[6] = 4$
$dp[16] = 1$
일반화하면 점화식은 다음과 같다.
$dp[n] = dp[i*i] + dp[n-i*i]$

$dp[i*i]$는 항상 1이므로 최소가 되는 $dp[n-i*i]$를 구해야 한다.

int[] dp = new int[N + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 1; i * i <= N; i++) {
    dp[i * i] = 1;
}

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

만약 $dp[18] = dp[16] + dp[2] = 2$를 구한다면 다음과 같이 반복한다.
$dp[18] = dp[1] + dp[17] = 3$
$dp[18] = dp[4] + dp[14] = 4$
$dp[18] = dp[9] + dp[9] = 2$
$dp[18] = dp[16] + dp[2] = 2$

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

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

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j * j < i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + dp[j * j]);
            }
        }
        System.out.println(dp[N]);
    }
}