백준 17626번 four squares (c++)

어떤 수를 제곱수의 합으로 표현할 때, 사용되는 최소 제곱수의 개수를 구하는 문제이다.

다이나믹 프로그래밍으로 문제를 해결할 수 있다.
n = (0, 1, 2, 3, ... n -1) + k²(k는 k² <= n 인 자연수) 의 형태로 n을 구하면서 최소 합이 만들어지는 경우를 dp에 저장하면된다.

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_NUM 50005
int dp[50005];

int main()
{
    int n;
    cin >> n;
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int localMin = MAX_NUM;
        for (int j = 1; j * j <= i; j++)
        {
            localMin = min(localMin, dp[i - j * j] + 1);
        }
        dp[i] = localMin;
    }
    cout << dp[n] << '\n';
    return 0;
}