[C++] 백준 17626번 Four Squares

모든 자연수는 제곱수 최대 4개로 만들 수 있다고 합니다.
자연수가 주어졌을 때 제곱수 최소 몇개로 그 자연수를 만들 수 있는지 구하는 문제입니다.

1부터 차례대로 최적의 수를 구해나갑니다.
그래서 n개일 때 i보다 작은 제곱수로 빼보고 그 때 남은 수의 최적 경우가 가장 적을 때
그 값 + 1을 해줌으로서 해당값의 대한 결과값을 구할 수 있습니다.
그리고 결과값을 저장하고 이를 반복해서 모든 값에 대한 최적수를 구할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAX 987654321
using namespace std;

int main(int argc, char* argv[])
{
	int n;
	int minNum;
	int DP[50010];
	vector<int> v;

	memset(DP, 0, sizeof(DP));

	cin >> n;


	DP[0] = 0;
	DP[1] = 1;

	for (int i = 1; i < 230; ++i) {
		v.push_back(i * i);
	}

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

		for (int j = 0; v[j] <= i; ++j) {
			int tmp = i - v[j];
			minNum = min(minNum, DP[tmp]);
		}

		DP[i] = minNum + 1;
	}

	cout << DP[n] << endl;

	return 0;
}