[BOJ] 1699 :: 제곱수의 합

https://www.acmicpc.net/problem/1699

다이나믹 프로그래밍으로 푸는 문제입니다.

다이나믹 프로그래밍을 생각할때 저는 항상 1차원 다이나믹인지, 2차원 다이나믹인지를 먼저 생각합니다.

이 경우에는 고려할 요건이 제곱수 밖에 없으므로 1차원으로 풀릴 것 같네요. 

1차원  dp[100001]개를 잡은 후에 

dp[i]의 조건을 정의합니다.

dp[i]는 i를 만드는데 필요한 제곱수의 최소 개수로 정의합니다.

그 후 점화식을 이용해 dp[i]를 구해야 합니다.

dp[i]를 구하기 위해선 i보다 작은 어떤 수 + 임의의 제곱수를 했을 때 i가 나오는 경우를 탐색해야 합니다.

때문에 i와 같거나 작은 경우까지 각각의 경우에 (i에서 제곱수를 뺀 수의 dp값 + 1) 과 현재 dp값을 비교해 나가면서 최솟값을 찾아야 합니다.

#include <iostream>
using namespace std;
int dp[100001];
//dp[i]는 i를 제곱수들의 합으로 표현할 때 항의 최소 개수
int main()
{
	int n;
	cin >> n;
	dp[0] = 0;
	dp[1] = 1;//dp 초기값
	
	for (int i = 2; i <= n; i++)
	{
		dp[i] = 1000001;
		for (int j = 1; j*j <= i; j++)
		{
			
			if (dp[i] > dp[i - j * j] + 1)
				dp[i] = dp[i - j * j] + 1;
		}
	}
	cout << dp[n] << endl;
}