백준 17626번 : Four Squares [C++]

주소 : https://www.acmicpc.net/problem/17626

17626번: Four Squares

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, num = 0;
	vector<int> dp(50001, 0);
	cin >> n;

	dp[1] = 1;

	for (int i = 1; i <= n; i++)
	{
		dp[i] = dp[1] + dp[i - 1];
		for (int j = 2; j * j <= i; j++)
		{
			dp[i] = min(dp[i], 1 + dp[i - j * j]);
		}
	}

	cout << dp[n] << '\n';
}

마무리 : 우리가 구하고 싶은 답은 최소 제곱수 합으로 표현하는 것이다. 처음 볼 때 dp를 이전 문제 풀 듯이 단순하게 짰는데 그러기에는 잘 되지 않았다.

 그래서 다른 방법으로 제곱수 합을 구하고 싶은거니까 입력값에 제곱수를 뺀 dp와 직접 구한 dp를 구하여 최솟값을 비교하여 출력하였다.