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

문제 링크

문제 설명

DP를 이용하여 문제를 해결하였다. dp1에는 1~루트 N의 제곱수를 저장하였고, dp2에는 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 저장하였다.

코드

#include <iostream>

#define MAX 987654321

using namespace std;

int num;

int dp1[400]; // n의 제곱을 저장
int dp2[100006];

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> num;

    for (int i = 1; i * i <= num; i++)
    {
        dp1[i] = i * i;
    }

    dp2[1] = 1;
    dp2[2] = 2;
    dp2[3] = 3;
    for (int i = 4; i <= num; i++)
    {
        dp2[i] = MAX;
        int sqrtnum;
        for (sqrtnum = 1; sqrtnum * sqrtnum <= i; sqrtnum++)
            ;
        sqrtnum--;
        for (int j = sqrtnum; j >= 1; j--)
        {
            if (j * j == i)
            {
                dp2[i] = 1;
                break;
            }
            dp2[i] = min(dp2[j * j] + dp2[i - j * j], dp2[i]);
        }
    }

    cout << dp2[num] << '\n';

    return 0;
}