백준 / 17626번 / Four Squares (dp)

[문제]

라그랑주는 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과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

[예제 입력]

25

[예제 출력]

1

[예제 입력]

26

[예제 출력]

2

[예제 입력]

11339

[예제 출력]

3

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] dp = new int[50001];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = 5;
        }

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

 

다이나믹 프로그래밍 문제이다.

규칙을 찾기 힘들어, 이런저런 포스팅을 많이 참고했다.

 

우선 입력값 n의 범위에 따라 dp[50001] 배열 하나를 선언한다.

그리고, dp[1] 부터 dp[8]까지의 경우를 직접 계산해봤다.

 

   dp[1] = 1

   dp[2] = dp[1] + 1 = 2

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

   dp[4] = 1

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

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

   dp[7] = dp[2^2] + dp[3] = 4 

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

 

1, 4, 9 등 제곱값부터 값이 변하게 되는 걸 알 수 있다.

식으로 나타내보면dp[i] = dp[i-j*j] + dp[j*j] 라고 할 수 있다.여기서 j*j는 i의 제곱수이다. (예로, i=8이면 j*j는 4)

 

또한, dp[j*j]의 경우는 1로 고정값이다. 왜냐하면, dp[j*j] 는 1, 4, 9등 어떠한 수를 제곱했을 때 나오는 수인데 dp[1], dp[4], dp[9]의 경우 모두 값이 1이기 때문이다.문제 자체가 제곱수들의 최소 "개수" 를 구하는 것이므로 dp[j*j]는 1이 되고,그렇게 되면 dp[i-j*j] + 1 => 이렇게 비교하면 된다!

 

한 가지 수에 제곱수의 합으로 표현할 수 있는 방법이 여러가지 있을 수 있는데,최소 개수를 구해야 하므로Math.min을 사용해 기존 dp[i] 값과 dp[i-j*j] + 1 값을 비교하면 된다.

 

또 주의할 점은, dp[i]와 비교를 해줘야 하기 때문에, 처음에 dp[i] 값을 초기화를 시켜줘야 한다.dp[0] = 0, dp[1] = 1로 해주고,for문을 돌며 2부터 N까지의 값은 5로 해주었다.

 

5로 초기화를 하는 이유는, 문제에 수를 넷 혹은 그 이하의 제곱수 합으로 나타내라고 했기 때문이다. (4가 최댓값)

 

 

---

 

 

아무래도 규칙을 찾는게 관건인 유형인데, 규칙을 찾는게 좀 어려웠다.

dp 문제를 앞으로 조금 더 부지런히 많이 풀어봐야겠다고 생각했다 !