[백준] 1699번: 제곱수의 합 - C++

문제

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

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

 

입력

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

 

출력

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

---

DP를 이용하여 풀 수 있는 문제.

처음에 접근했던 방식은 N보다 작은 수 중 가장 큰 제곱수부터 빼나가는 방식이었는데, 그렇게 했더니 답이 다르게 나오는 경우들이 많았다. 어쨌거나 답이 제대로 나오지 않는다는 것은 접근 방식이 틀렸다는 것이기 때문에, 다른 방법을 생각해줘야한다.

 

구글의 힘을 빌린 결과, 제곱수 항의 최소 개수를 구해주는 방식은 다음과 같다.

1부터 N까지의 제곱수 항의 최소 개수를 담을 배열 D[]를 선언해주고, i = j² + (i - j²) 인 점을 이용하여 N보다 작은 수 중 가장 큰 제곱수부터가 아닌, 가장 작은 1부터 빼가며 가장 최소가 되는 D[i]의 값을 비교한다.

이 때, D[j²]는 항상 1이 되기 때문에 기존의 D[i]와 D[i - j²] + 1의 값을 비교해가며 항이 최소 개수가 되는 경우를 저장해준다.

 

항상 D[i]는 i보다 작은 값이 되기 때문에, 처음에는 D[i] = i로 초기화해준다.

18을 예로 들어보자.

 

1. D[18] = min(D[18], D[17] + 1), D[17] = 2 ( 4² + 1² )

    D[18] = min(18, 3) = 3

2. D[18] = min(D[18], D[14] + 1), D[14] = 3 ( 3² + 2² + 1² )

    D[18] = min(3, 4) = 3

3. D[18] = min(D[18], D[9] + 1)

    D[18] = min(3, 2) = 2

4. D[18] = min(D[18], D[2] + 1)

    D[18] = min(2, 3) = 2

 

따라서, D[18] = 2 ( 3² + 3² )가 된다.

 

코드

#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int DP(int num);
int min(int a, int b) { return a < b ? a : b; }

int main(void) {
    int n;
    scanf("%d", &n);
    printf("%d\n", DP(n));
    return 0;
}

int DP(int num) {
    vector<int> D(num + 1, 0);
    for(int i = 1; i <= num; i++) {
        D[i] = i;
    }

    for(int i = 1; i <= num; i++) {
        for(int j = 1; j * j <= i; j++) {
            D[i] = min(D[i], D[i - j * j] + 1);
        }
    }
    return D[num];
}