[백준 BOJ][C++]1699번 제곱수의 합 풀이: DP

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

1699번: 제곱수의 합

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 dp[n]은 n을 제곱수들의 합으로 표현할 수 있는 최소 항의 개수를 나타냅니다. 

 

점화식부터 보겠습니다. 

 

dp[n]=min(dp[n], dp[n-i*i]+1), (1<= i*i <= n)

 

 1 = 1^2

 2 = 1^2+1^2

 3 = 1^2+1^2+1^2

 

이므로 dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3 으로 초기화 합니다. 

 

4 = 2^2 이므로 dp[4]=2입니다. 이 결과가 어떻게 도출되는지 한 번 보겠습니다. 

 

dp[4-1*1]=dp[3]	3
dp[4-2*2]=dp[0]	0

 

 이 때의 최솟값은 0이므로 dp[4]의 값은 0+1이 되겠죠?

 

 

11 = 3^2+1^2+1^2 이므로 dp[11]=3 입니다. 

dp[11-1*1]=dp[10]	2
dp[11-2*2]=dp[7]	4
dp[11-3*3]=dp[2]	2

이 때의 최솟값은 2이므로 dp[11]의 값은 2+1이 됩니다. 

 

 

다음은 전체 코드입니다. 

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>

using namespace std;

#define MAX 100001

int dp[MAX];
int N;

int main(void) {

	cin >> N;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;

	for (int i = 4; 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];

	return 0;
}