백준 1699 c++

처음 풀은 방식은 N에 가장 가까운 제곱수를 차례로 빼기 때문에 같은 크기의 제곱수의 합에 대해서는 확인을 하지 못해서 오답이 발생했다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
int find_answer(int N)
{
	int i = 1;
	int count = 0;

	while (N != 0)
	{
		if (i * i == N)
		{
			count++;
			break;
		}
		else if (i * i > N)
		{
			N = N - (i - 1) * (i - 1);
			i = 1;
			count++;
		}
		else
		{
			i++;
		}
	}

	return count;
}
*/

int find_answer(int N)
{
	int i, j;
	vector<int> v;

	for (i = 0; i <= N; i++)
	{
		v.push_back(i);
	}
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j * j <= i; j++)
		{
			v[i] = min(v[i], v[i - j * j] + 1);
		}
	}

	return v[N];
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int  N;
	
	cin >> N;
	cout << find_answer(N) << "\n";

	return 0;
}