1699 제곱수의 합

1699. 제곱수의 합 / c++ / Silver2 / 36분

문제

https://www.acmicpc.net/problem/1699

1. 100’000 이하의 자연수 N이 주어진다.
2. N을 제곱수의 합으로 표현할 때, 가장 짧은 길이는?

접근 방식

동적 프로그래밍

1. 우선 최대 i * i <= N인 제곱수들을 구해서 dp[i*i] = 1; 을 해준다.
2. 그 다음 그 i * i를 벡터에 넣어준다.
3. 다음 DP(N)을 해주는데
   1. dp[N] == 1 이면 출력
   2. 아니라면 vector에서 lower_bound로 N보다 작은 제곱수의 위치 i를 뽑는다.
   3. for (i;i>=0;–i) 로 제곱수들을 내림차순으로 순회하면서 DP(vector[i]) + DP(num - vector[i])의 값 중 최소값을 저장한다.
   4. 저장된 값 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
inline int MIN(int A, int B) { return A < B ? A : B; }
int N;
int dp[100'001] = {};
vector<int> powVec;

int DP(int num)
{
    if (dp[num] == 0)
    {
        int minNum = 987'654'321;
        int startNum = lower_bound(powVec.begin(), powVec.end(), num) - powVec.begin();
        if (startNum == powVec.size() || powVec[startNum] > num) startNum--;
        for (int i = startNum; i >= 0; --i)
        {
            minNum = MIN(minNum, DP(powVec[i]) + DP(num - powVec[i]));
        }

        dp[num] = minNum;
    }

    return dp[num];
}

int main()
{
    cin >> N;

    int sqrtNum = sqrt(100'000);
    for (int i = 1; i <= sqrtNum; ++i)
    {
        int powNum = i * i;
        dp[powNum] = 1;
        powVec.push_back(powNum);
    }

    cout << DP(N) << '\n';

    return 0;
}

다시 생각해 볼 점

1. 일일히 i (1~N-1) 을 구해서 DP(N) + DP(N-i)를 하기보다,
   미리 제곱수를 구해서 저장해놓고, N보다 작은 제곱수부터 내림차순으로 순회하는 발상이 좋았다고 생각한다.
2. 다만 이 문제를 더 빨리 푼 사람들의 코드를 보니 ‘에라토스테네스의 체’처럼 미리 순회를 돌면서 dp를 다 채워넣고 마지막에 dp[N]을 사용했다.
3. 결국 핵심은 제곱수 + 제곱수 이란걸 생각하고, 숫자가 크지 않다면 미리 에라토스테네스의 체 처럼 dp를 먼저 채워볼 생각을 해야겠다.