[BOJ / C++] 1699번 : 제곱수의 합

문제

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

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

입력

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

출력

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

Solved.ac 레벨

실버 II

풀이

#include <bits/stdc++.h>
#define MAX 100001

using namespace std;

int n;
int dp[MAX];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

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

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

    cout << dp[n] << '\n';

    return 0;
}

dp 배열에 들어갈 값은 해당 숫자를 제곱수의 합으로 나타냈을 때 제곱수의 개수의 최소값이다. 수기로 작성하며 나열해보니...

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 1
dp[5] = 2
dp[6] = 3
dp[7] = 4
dp[8] = 2
.
.
.

별다른 규칙을 찾기가 힘들었다.

 

하지만 최소값만 가지고 생각하다보니 모든 숫자 n은 1^2를 n개만큼 더하면 제곱수의 개수를 최대로 할 수 있다. 따라서 dp 배열의 모든 원소는 해당 원소의 인덱스 i로 초기화시켜주면 된다.

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

그리고 이중 for문 (i, j)을 돌리며 dp 배열을 탐색하며 캐시를 이용해 최소값을 새로이 저장하게 된다. dp[4] 즉, n이 4인 경우로 예를 들어 보자.

 

dp[4]는 dp 배열 탐색 전 4로 초기화 되어있다.

4 = 1^2 + 1^2 + 1^2 + 1^2

이 dp[4]를 j = 2부터 올라오면서 j의 제곱이 4보다 작을때까지 반복한다

처음에는 j^2를 활용할 줄 몰라 out of bounds 오류를 맛봐야 했다. 하지만 j^2는 8과 9에도 적용이 된다는 것을 깨달았다.

for(int i = 2; i <= n; i++){ //i = 4
        for(int j = 2; j*j <= i; j++){
        // j = 2 * 2 = 4
            dp[i] = min(dp[i], dp[i-j*j] + 1);
            //dp[4] = min(dp[4], dp[4 - 4] + 1
            //dp[4] = min(4, 1)
            //dp[4] = 1
        }
    }

어쨌든 실버 2 치고는 수학적으로 생각할 필요가 있어서 점화식이 쉽게 나오지 않아 어려웠다.

1699번: 제곱수의 합