sum_sq.cpp

#include <iostream>
#include <set>
#include <vector>
#include <math.h>

using namespace std;

int sum_sq(int n) {
    int n_sqrt = sqrt(n);
    set<int> sqrs;
    for (int i = 1; i <= n_sqrt; ++i)
        sqrs.insert(i * i);
    vector<int> dp(n + 1);
    dp[0] = 0;
    int curr = 1;
    for (int i = 1; i <= n; ++i) {
        if (sqrs.count(i)) curr = i;
        dp[i] = 1 + dp[i - curr];
    }
    return dp[n];
}

int main() {
    int i;
    cin >> i;
    cout << sum_sq(i) << endl;
}