BOJ 백준 1699 제곱수의 합 <dp>

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

< 제곱수의 합 >

  이 문제는 100000 이하의 정수 하나를 입력 받아, 그 정수를 제곱수의 합으로 표현할 때, 사용되는 제곱수의 최소 개수를 출력해주는 문제이다.

dp문제로, 1부터 입력받은 정수 N까지 최소 개수를 구해나가면 된다.'

1은 1^2로 1개

2는 1^2 + 1^2 로 2개

3은 1^2 + 1^2 + 1^2 로 3개

4는 2^2 로 1개

...

이렇게 dp배열을 채워 나가, dp[N]을 출력해주면 된다.

dp 배열을 채워나가는 점화식은 아래와 같다.

dp[i] = min(dp[i], dp[i - 제곱수] + 1)

i - 제곱수 + 제곱수 = i 이다.

예를 들어, 12는  [3 + 9] , [8 + 4] , [11 + 1] 로 표현될 수 있는 것이다.

즉, dp[i] = dp[i - 제곱수] + dp[제곱수] 로 표현할 수 있고, dp[제곱수]는 당연히 특정 정수의 제곱수로 표현이 되므로 1개로 표현이 가능하다.

따라서 dp[제곱수] = 1 이므로, dp[i] = dp[i - 제곱수] + 1 이 되는 것이다.

예를 든 12에서 3가지의 경우가 있으므로, 3가지의 경우를 모두 검사하여 최소 개수를 dp 배열에 저장해주면 된다.

#include <iostream>
#define SIZE 100001
#define MIN(a, b) a < b ? a : b

using namespace std;

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

	int dp[SIZE] = { 0 };
	int n, num = 1;

	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		dp[i] = i;
		for (int j = 1; j*j <= i; ++j)
		{
			dp[i] = MIN(dp[i], dp[i - j * j] + 1);
		}
	}
	cout << dp[n] << '\n';

	return 0;
}