DP

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5+5;
ll n,dp[N];
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
        dp[i] = 1e9;
    dp[0] = 0,dp[1] = 1;
    for(ll i = 2;i<=n;i++)
    {
        for(int j = 1;j<=sqrt(i);j++)
        {
            if(i-j*j>=0)
                dp[i] = min(dp[i],dp[i-j*j]+1);
        }
    }
    cout<<dp[n];
    return 0;
}