[백준 1699] 제곱수의 합 (DP) (C/C++)

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
 
int N;
int dp[100010];
 
int solve(int num)
{
    if(num == 0)
    {
        return 0;
    }
    
    if(dp[num] != 999999)
    {
        return dp[num];
    }
    
    for(int i = sqrt(num); i >= 1; i--)
    {
        int squared = pow(i, 2);
        
        dp[num] = min(dp[num], solve(num-squared)+1);
    }
    
    return dp[num];
}
 
int main(void)
{
//    freopen("B1699_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < 100010; i++)
    {
        dp[i] = 999999;
    }
    
    cout << solve(N);
    
    return 0;
}