N보다 작거나 같은 제곱수 중에서 가장큰 값을 빼가면서 값을 구했다.
즉
void sol(int a)
{
if (a == 0)
{
return;
}
int tmp = cal(a);
sol(a - (tmp * tmp));
count +=1;
12 = 2^2 +2^2 +2^2 으로 3이나오지만, 잘못된 풀이는 12가 나오게된다.
가장 큰 제곱수로 빼는것은 가장작은 답을 추출해 내지 못한다.
어떤수의 제곱을 더해서 만드는 수니까, 어떤수의 제곱을 더하기 전의 값에 단서가 있을것이다.
dp[i]의 최대값은 i이고, dp[i] = min(dp[i-n^2]+1,dp[i])이다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
using namespace std;
#define endl "\n"
#define MAX 100000+1
int N;
int dp[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> N;
for (int i = 1; i <= N; i++)
{
dp[i] = i;
for (int j = 1; j * j <= i; j++)
{
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[N];
}