[백준] 17626번: Four Squares (Java)

1. 문제설명

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다.

ex) 26은 5^2 + 1^2 또는 4^2 + 3^2 + 1^2

자연수 n이 주어질 때, n의 제곱수 합이 최소 개수가 되는 값을 구하는 문제이다.

• 시간 제한: 0.5초
• 메모리 제한: 512MB

 

2. 접근 방식

• DP 방식을 사용한다. dp 배열을 사용한다. dp[i]는 숫자 i를 4개 이하의 제곱수 합으로 표현할 때 필요한 제곱수의 최소 개수를 저장한다.
• dp[0] = 0, dp[1] = 1로 초기화한다. 0은 제곱수가 필요 없고, 1은 1^2 하나로 표현 가능하기 때문이다.
• 2부터 n까지 모든 숫자 i에 대해:
  • i보다 작거나 같은 모든 제곱수(j*j)에 대해 검사한다.
  • i에서 제곱수(j*j)를 뺀 나머지(temp)에 대한 dp 값 중 최소값을 찾는다.
  • 최소값에 1을 더해서 dp[i]에 저장한다.
• dp[j]이 결과값이 된다.

 

참고) https://steady-coding.tistory.com/18

예제 N = 4
먼저, dp[0] = 0, dp[1] = 1인 상태로 초기 상태를 설정합니다.
그 다음 2부터 쭉 위 식을 이용하여 해를 구해보겠습니다.
2보다 작거나 같은 제곱수는 1이 있고, dp[1] 에 1을 더해주면 됩니다.
따라서, dp[2] = 1 + 1 = 2가 됩니다.
3보다 작거나 같은 제곱수는 1이 있고,  dp[2]에 1을 더해주면 됩니다.
따라서, dp[3] = 2 + 1 = 3이 됩니다.
4보다 작거나 같은 제곱수는 1, 2가 있고, dp[3], dp[0] 중 작은 값을 택한 뒤, 1을 더해주면 됩니다.
이 중 작은 것은 dp[0] = 0 이므로 dp[4] = 0 + 1 = 1이 됩니다.
따라서, 4의 최소 제곱수의 개수는 4개입니다.

 

 

3. 틀린 이유 설명

처음에는 백트래킹 방법을 사용해 해결하려고 했다.

// main에서 find(1, 0) 호출
static void find(int s, long num) {
    System.out.println("num="+num);
    if(num > n || count > 4) return;
    if(num == n) {
        if(count < min) min = count;
    }

    for(long i=s; i<n/2; i++) {
        num += i*i; count++;
        if(count <= 4) find(s+1, num);
        num -= i*i; count--;
    }
}

이 방법은 작은 숫자(25, 26)에 대해서는 정답을 출력했지만,
큰 숫자(11339, 34567)에 대해서는 시간 초과로 인해 정답을 출력하지 못했다.

 

4. 올바른 접근 방식 및 해결 방식

• 이 문제는 DP를 사용하는 것이 적절하다.
  • 부분 문제의 중복: 큰 수의 해를 구할 때, 작은 수의 해를 반복적으로 사용.
  • 최적 부분 구조: n을 표현하는 최적해는 n보다 작은 수들의 최적해로부터 구할 수 있음.
• 즉, n을 4개 이하의 제곱수 합으로 표현하는 방법의 수는 n보다 작은 수들의 해결책을 이용해 구할 수 있다.

 

5. 최종 코드

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];
        dp[0] = 0; dp[1] = 1;

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

            dp[i] = min+1;
        }

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

 

6. 시간복잡도

$O(n \sqrt n)$

 

7. 느낀점 or 기억할정보

큰 수에 대한 반복적인 계산이 필요한 경우, 백트래킹보다 DP가 효율적일 수 있다.

DP의 핵심은 부분 문제의 해를 저장하고 재사용하는 것이다.