공log/[P&B]

[P&B] #118 BAEKJOON 17626

ming_OoO 2023. 10. 14. 19:41
728x90

백준 17626번 JAVA Four Squares

문제 설명

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

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

 

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.io.*;
public class bj17626 {
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        solve(n);

        bw.write(String.valueOf(dp[n]));
        bw.flush();
    }

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

 

문제 풀이 코멘트

먼저 n의 제곱수들의 최소 개수 합을 저장한 배열을 16까지 나열해보면 아래와 같습니다.

dp[1] = 1^2 = 1개

dp[2] = 1^2 + 1^2 = 2개

dp[3] = 1^2 + 1^2 + 1^2 = 3개

dp[4] = 2^2 = 1개

dp[5] = 2^2 + 1^2 = 2개

dp[6] = 2^2 +1^2 + 1^2 = 3개

dp[7] = 2^2 +1^2 + 1^2 + 1^2 = 4개

dp[8] = 2^2 + 2^2 = 2개

dp[9] = 3^2 = 1개

dp[10] = 3^2 + 1^2 = 2개

dp[11] = 3^2 + 1^2 + 1^2 = 3개

dp[12] = 3^2 +1^2 + 1^2 + 1^2 = 4개

dp[13] = 3^2+2^2 = 2개

dp[14] = 3^2+2^2 + 1^2 = 3개

dp[15] = 3^2+2^2 +1^2 + 1^2 = 4개

dp[16] = 4^2 = 1개

...

 자연수 n을 만들기 위해 필요한 최소 개수의 제곱수 합을 계산하려면, 작은 수부터 시작해서 큰 수까지 차례로 계산해보면서 최소값을 구해야 합니다. 이것이 동적 프로그래밍의 핵심 아이디어입니다.

 dp[i]는 i를 만드는데 필요한 최소 개수의 제곱수 합을 나타냅니다. 따라서 dp[i]를 계산하기 위해 i보다 작은 숫자들을 활용하여 계산합니다. 각 i에 대해서, 가능한 모든 j에 대해 dp[i]를 계산합니다. 여기서 j는 1부터 시작해서 j * j <= i, 즉 i보다 작거나 같은 최대의 제곱수의 제곱근 j까지 증가합니다.

dp[i]를 계산할 때, i - j * j를 만드는데 필요한 최소 개수를 이미 알고 있기 때문에, dp[i - j * j] 값을 활용하여 dp[i]를 업데이트합니다. 예를 들어 dp[7]의 경우 7보다 작거나 같은 제곱수는 4(j=2, j*j=4)입니다. 7에서 4를 빼면 3인데 3을 만들기 위한 최소의 제곱수 개수는 dp[3], 즉 3개입니다. 3을 만들기 위한 최소의 제곱수 개수 + j*j를 의미하는 1개  = 3 + 1로 총 4개입니다. (dp[7] = 4)

다시 말해, dp[i]는 dp[i - j * j] 중에서 가장 작은 값을 찾아내고, 거기에 1을 더해주면 됩니다. 이것은 i - j * j를 만드는데 필요한 최소 개수에 j * j 하나를 더하면 i를 만들기 위한 최소 개수가 됩니다.

 

코드를 설명해보겠습니다.

  1. 먼저 dp 배열을 초기화합니다. dp[0]은 0을 만드는데 필요한 최소 개수이므로 0, dp[1]은 1을 만드는데 필요한 최소 개수이므로 1로 초기화합니다.
  2. solve 함수는 동적 프로그래밍을 사용하여 dp 배열을 채우는 역할을 합니다. 주요 루프는 for (int i = 2; i <= n; i++)로 시작합니다.
  3. 내부 루프 for (int j = 1; j * j <= i; j++)는 현재 숫자 i를 만들기 위해 필요한 제곱수의 개수를 계산합니다. j는 1부터 시작하며 j * j가 i 이하인 제곱수를 순차적으로 확인합니다.
  4. 각 j에 대해, dp[i - j * j]는 i - j * j를 만드는데 필요한 최소 개수입니다. min 변수를 사용하여 최소 개수를 업데이트합니다. 따라서 min은 모든 가능한 j에 대한 dp[i - j * j] 중 가장 작은 값을 가지게 됩니다.
  5. dp[i]는 min + 1로 설정됩니다. 왜냐하면 i를 만들기 위해 min만큼의 제곱수를 사용하고, 추가적으로 하나의 제곱수(= j * j)를 더 사용해야 하기 때문입니다.
  6. 위의 루프가 끝나면 dp[n]에는 주어진 자연수 n을 최소 개수의 제곱수 합으로 나타내는데 필요한 최소 개수가 저장됩니다.

브루트포스 법은 사용하지 않았지만 동적 프로그래밍으로 풀어본 방법이었습니다.

728x90
댓글수1