Timus-1073. Square Country

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define F first
#define S second
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > V;
typedef map<int, int > mp;
#define debug cout << -1 << endl;
#define REP(i, a, b) for(int i=a; i<b; i++)
#define pop pop_back
#define sz(a) (int)a.size()
const ll MOD = 1000000007;
const int maxN = 2001;

int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};

void solve()
{
    int x;
    cin >> x;
    vector< int > v;
    int i = 1;
    while(i*i<=x) {
        v.pb(i*i);
        //cout << i*i << endl;
        i++;
    }
    int n = sz(v);
    int dp[n+1][x+1];
    for(int i=0; i<=n; i++) {
        dp[i][0] = 0;
        for(int j=1; j<=x; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=x; j++) {
            if(v[i-1]<=j) {
                dp[i][j] = min(1+dp[i][j-v[i-1]],dp[i-1][j]);
            }
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][x] << endl;
    return;
}

int main()
{
    FastIO;
    //freopen("tttt.in","r",stdin);
    //freopen("tttt.out","w",stdout);
    int t;
    t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}