[백준 17626 : JAVA] Four Squares

1. 문제

---

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

2. 입력

---

입력은 표준입력을 사용한다. 입력은 자연수 $n$을 포함하는 한 줄로 구성된다. ($1 \le n \le 50000$)

3. 출력

---

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

4. 풀이

---

유명한 DP 입문용 문제입니다. 

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}$

 

점화식은 다음과 같습니다.

f(n) = f(n - m*m) + 1 

 

처음에 제가 실수한 부분은 위 점화식에서 m*m이 n보다 작거나 같은 가장 큰 수로 잡은 것이었습니다.
위와 같이 하게되면 다음의 반례가 존재합니다.

f(12) = f(12 - 3*3) + 1
즉, 12 = $3^{2}+1^{2}+1^{2}+1^{2}$가 되지만, 12 = $2^{2}+2^{2}+2^{2}$이 최소 개수입니다.

 

따라서, min 함수로 가장 작은 값을 구해줘야 합니다. (코드로 확인해보세요. 🙂 )

5. 코드

---

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

public class Main {

    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(in.readLine());
        dp = new int[N + 1];
        bottomUp();
        System.out.println(dp[N]);
    }

    private static void bottomUp() {
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = 0x7fffffff;
            for (int j = 1; j * j <= i; j++) {
                int idx = i - j * j;
                dp[i] = Math.min(dp[i], dp[idx] + 1);
            }
        }
    }
}