제곱수의 합

---

잘못된 풀이

N보다 작거나 같은 제곱수 중에서 가장큰 값을 빼가면서 값을 구했다.
즉

void sol(int a)
{
	if (a == 0)
	{
		return;
	}
	int tmp = cal(a);
	sol(a - (tmp * tmp));
    count +=1;

반례 12

12 = 2^2 +2^2 +2^2 으로 3이나오지만, 잘못된 풀이는 12가 나오게된다.

가장 큰 제곱수로 빼는것은 가장작은 답을 추출해 내지 못한다.

---

올바른 풀이 (DP)

어떤수의 제곱을 더해서 만드는 수니까, 어떤수의 제곱을 더하기 전의 값에 단서가 있을것이다.

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];
}

참고

https://lmcoa15.tistory.com/43