[C++] 백준 17626 Four Squares

#include <iostream>
#include <vector>
 
int DP[50001] = {};
 
int main() 
{
	int N = 0;
	std::cin >> N;
 
	for (int i = 1; i * i <= N; ++i) 
	{
		DP[i * i] = 1;
	}
 
	for (int i = 1; i <= N; ++i)
	{
		if (DP[i])
		{
			continue;
		}
 
		for (int j = 1; j * j <= i; ++j)
		{
			if (!DP[i])
			{
				DP[i] = DP[j * j] + DP[i - j * j];
			}
 
			else
			{
				DP[i] = std::min(DP[i], DP[j * j] + DP[i - j * j]);
			}
		}
	}
 
	std::cout << DP[N];
 
	return 0;
}

DP로 전부 구해야되는 문제였습니다.

처음에는 위에서 내려오면서 가장 높은 제곱 수로 구하려고 했는데 바로 틀리더라구요.

DP로 계산해가면서 풀어야합니다. 처음에 제곱수 들은 무조건 1개로 해서 나오는 걸로 했구요.

처음에 DP[i]가 있는 경우는 바로 제곱수 이기 때문에 계산할 필요가 없고 

DP[i]번 째를 구하기 위해서는 

예를 들어, DP[30]의 수는 DP[25] + DP[5], DP[16] + DP[14], DP[9] + DP[21], DP[4] + DP[26]와 같습니다.

이와 같은 방법으로 계속해서 N까지 계산하면서 풀어야 합니다.