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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1699번 문제인 제곱수의 합이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

Lagrange's four-square theorem(라그랑주의 네 제곱수 정리)에 따르면, 모든 음이 아닌 정수는 (0을 포함한) 4개의 제곱수의 합으로 표현이 가능하다.

 

그렇다면 어떤 수 n이 주어졌을 때 그 수를 최소 몇 개의 (0이 아닌) 제곱수의 합으로 나타낼 수 있는지는 어떻게 구할 수 있을까?

 

처음에는 직관으로 다음과 같은 알고리즘을 구상했다.

 

#1)

 

1) n 이하 제곱수들을 구한다. 이들은 1개의 제곱수의 합으로 나타낼 수 있다고 기록한다.

이중 n이 있다면 1을 출력한다.

2) n 이하 제곱수의 합으로 나타낼 수 있는 수(단, 1에서 구한 수 제외)들을 구한다. 이들을 제곱수의 합으로 나타내기 위해서는 최소 2개의 제곱수가 필요하다(그리고 가능하다)고 기록한다.

이중 n이 있다면 2를 출력한다.

3) 1에서 기록한 수와 2에서 기록한 수의 합으로 나타나는 수(단, 1과 2에서 구한 수 제외)들을 구한다. 이들을 제곱수의 합으로 나타내기 위해서는 최소 3개의 제곱수가 필요하다(그리고 가능하다)고 기록한다.

이중 n이 있다면 3을 출력한다.

4) 1, 2, 3에서 등장하지 않은 수는 Lagrange's four-square theorem에 따라 4개의 제곱수가 필요하다. 그러므로 4를 출력한다.

 

다음은 위의 알고리즘을 구현해 제출한 것이다.

 

#include <iostream>
using std::cin;
using std::cout;

bool nums[100001][4];

int main()
{
    int n;
    cin >> n;
    for (int i = 1;i * i <= n;i++) {
        nums[i * i][1] = true;
    }
    for (int i = 1;i <= n;i++) {
        if (nums[i][1]) {
            for (int j = i;j <= n-i;j++) {
                if (nums[j][1] and !nums[i + j][1]) {
                    nums[i + j][2] = true;
                }
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        if (nums[i][2]) {
            for (int j = 1;j <= n-i;j++) {
                if (nums[j][1] and !nums[i+j][1] and !nums[i+j][2]) {
                    nums[i + j][3] = true;
                }
            }
        }
    }
    if (nums[n][1]) cout << 1;
    else if (nums[n][2]) cout << 2;
    else if (nums[n][3]) cout << 3;
    else cout << 4;
}

 

이 알고리즘이 틀린 것은 아니나, 소요시간이 다른 사람들에 비해 매우 긴 것을 확인했다. (876ms)

그 이유를 생각해본 결과, n을 제곱수의 합으로 나타낼 수 있지 고려할 때 고려해보지 않아도 될 수까지 전부 탐색하는 것이 원인이라고 결론 내렸다. 따라서, 고려해볼 필요가 있는 수만 다루기 위해 recursion을 이용한 DP를 이용하여 다시 시도해봤다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
using std::min;

bool visited[100001];
int times[100001];

int dp(int n) {
    int ret = 4; // 많아봤자 4개의 제곱수의 합으로 표현 가능
    for (int i = 1;i * i <= n;i++) { 
        if (visited[n - i * i]) { //memoization: 계산했던 값은 먼저 계산한 값 반환
            ret = min(ret, times[n - i * i] + 1);
        }
        else {//아직 안 계산해본 값이라면 계산해보기
            times[n - i * i] = dp(n - i * i);
            visited[n - i * i] = true;
            ret = min(ret, times[n - i * i] + 1);
            // ret = min("n에서 --n이하의 제곱수를 뺀 것-- 을 만드는데 필요한 제곱수의 최소 개수)
        }
    }
    return ret;
}

int main()
{
    visited[0] = true;
    int n;
    cin >> n;

    bool chk = false;
    for (int i = 1;i * i <= n;i++) {
        visited[i * i] = true;
        times[i * i] = 1;
        if (i * i == n) {
            chk = true;
        }
    }

    if (chk) cout << 1;
    else {
        int ans = dp(n);
        cout << ans;
    }
    return 0;
}