1699 제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=$3^2$+$1^2$+$1^2$(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=$2^2$+$2^2$+$1^2$+$1^2$+$1^2$(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1

7

예제 출력 1

4

예제 입력 2

1

예제 출력 2

1

예제 입력 3

4

예제 출력 3

1

예제 입력 4

11

예제 출력 4

3

예제 입력 5

13

예제 출력 5

2

코드

import java.io.*;

public class P_1699 {
    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());
        int[] dp = new int[n + 1];
        int cnt = 0;

        for (int i = 1; i<= n; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = (dp[i] < dp[i - j * j] + 1) ? dp[i] : dp[i - j * j] + 1;
            }
        }
        bw.write(Integer.toString(dp[n]));
        bw.flush();
    }
}

코드 내용

처음에는 dp말고 그리디로 풀었는데 41 = 36 + 4 + 1로 계산을 해 버려서 오답이 나왔다.
41 = 25 + 16으로 계산해야 최소 개수가 나오기 때문이다.

그래서 dp를 이용했는데 현재 수에서 제곱수를 뺐을 때의 결과 dp에 +1을 해 주면 현재 수의 dp를 구할 수 있다는 점에서 점화식을 구했다.
수를 구할 땐 제곱수를 더해가면서 구해야하기 때문이다.

dp[i]는 i 즉, 구하려는 수로 초기화를 해 주고 시작을 했고 제곱수를 뺀 dp로 연산을 할 때마다 최솟값 비교로 업데이트를 해 주었다.

만약, 41을 예로 들자면 dp[i]의 초기값은 41이고 dp[i - 1^1]인 dp[40]의 값에 +1을 해 준 값과 비교를 하는 것이다.
그러므로 dp[i]와 dp[i - j*j]를 비교하게 된다.
이 때, j*j가 i를 넘어가게 되면 인덱스가 음수가 되어버리므로 j*j가 i보다 작거나 같을 경우에만 연산을 할 수 있도록 조건을 달아주었다.