[백준/BOJ] 백준 17626번 : Four Squares

www.acmicpc.net/problem/17626

17626번: Four Squares

n이하의 수들을 제곱한 값을 미리 저장해 놓은 뒤, 각각의 수가 n을 제곱수의 합으로 표현될 때 제곱수로 사용하는지 확인하여, n을 제곱수의 합으로 표현할 때 제곱수의 개수가 최소가 되는 개수를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> number2(50001, 0);
vector<int> cache(50001, -1);

int Solve(int number)
{
	int& ret = cache[number];

	if (ret != -1)
		return ret;

	if (number == 0)
		return 0;

	ret = 987654321;

	for (int i = 1; number2[i] <= number; i++)
	{
		ret = min(ret, Solve(number - number2[i]) + 1);
	}

	return ret;
}

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

	int n;
	cin >> n;

	//n이하 수들의 제곱을 계산해서 저장해 놓는다
	for (int i = 1; i <= n; i++)
	{
		number2[i] = i * i;
	}

	cout << Solve(n);

	return 0;
}