[BOJ 17626] Four Squares - Java

풀이

해설

자연수 N이 주어지고, N을 구성할 수 있는 제곱수들의 수를 구하는 문제이다.
모든 자연수는 최대 자연수 4개의 제곱수의 합으로 표현할 수 있다고 라그랑주에 의해 증명이 되었다.

나의 경우 문제의 자연수를 제곱수가 2이상인 자연수로 착각해서 오래걸렸다.

풀이 과정은 다음과 같다.

 

1. 배열에 1부터 N까지의 값을 저장한다.
2. (i-j^2)+1 값을 사용해 값을 구해나간다. i는 1부터 N까지 순회하는 자연수를 의미한다.

 

1번의 의미를 1*1의 값의 개수라고 생각해보자. 그리고 배열을 돌면서 (i-j^2)+1를 적용시킨다. 이것을 다음과 같은 코드로 적용시킬 수 있다.

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

• 구할 수 있는 자연수의 최소개수을 출력하는 조건이었기 때문에 최소개수을 구한다.
• dp[i - j*j] + 1 을 구하면서 dp배열을 순회했다면, 해당 배열에는 자연수(i)에 대한 자연수의 최소 개수가 저장될 것이다.
  • dp[i]에는 i를 구할 수 있는 자연수의 개수가 들어있다.
  • 변경되지 않았다면 i에 해당하는 자연수가 들어있을 것이다.
  • dp[i - j*j]는 j*j에 해당하는 자연수의 개수를 빼는 작업과 같다.
  • 즉, j*j에 해당하는 자연수를 제곱근으로 보고 +1로 치환하는 것으로 생각하면 된다.

시간복잡도

2중 for문을 사용하여 1부터 N까지의 최소 제곱 수의 개수를 구한다.
바깥쪽의 반복문은 N번 실행되고, 내부의 반복문은 i의 제곱근까지 실행된다.

따라서 시간복잡도는 O(NrootN)이다.

코드

package ForSquares_17626;

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());
        br.close();

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

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

Reference

• 문제