백준 1699번 C++

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

const int MAX = 100001;

int n;

int sumcount[MAX];

int minnum() {

for (int i = 2; i <= n; i++) {

if (sumcount[i] == 1)

continue;

int result = 987654321;

for (int j = (int)sqrt(i); j >= 1; j--){

int mins = 1 + sumcount[i - (j*j)];

if (result > mins) {

result = mins;

sumcount[i] = result;

}

}

}

return sumcount[n];

}

int main(void) {

cin >> n;

memset(sumcount, 0, sizeof(sumcount));

for (int i = 1; pow(i, 2) <= n; i++) {

sumcount[i*i] = 1;

}

cout << minnum();

}