[C/C++] 백준 17626번 - Four Squares

<코드>

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

int n;
int dp[50001];

int main() 
{
	ios::sync_with_stdio(0); 
	cin.tie(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];
}

풀이 방법

예시 : dp[101]을 구하는 방법
dp[1] + dp[100]
dp[4] + dp[97]
dp[9] + dp[92]
dp[16] + dp[85]
...
dp[64] + dp[37]
dp[81] + dp[20]
이중에서 가장 작은 값을 고르면 됩니다.
(dp[1], dp[4], dp[9] 등등 제곱수인것은 모두 값이 1이다.)
www.acmicpc.net/problem/17626

17626번: Four Squares