[동적계획법, 난이도 중] 백준 1699번 제곱수의 합

n을 제곱수들의 합으로 나타낼 수 있는 경우가 여러개 있을 때, 가장 적은 제곱수들을 가지는 경우를 찾으면 된다.

 

정수 i보다 낮은 정수 j에 제곱수 하나를 더하여 i를 만들 수 있을 때, j값으로는 i-1^2, i-2^2, i-3^2.. 등이 올 수 있다. 

각 j값들을 제곱수들의 합으로 표현할 수 있을 때, 이 제곱수 항의 각 최소 개수들의 최솟값에, 특정 제곱수를 의미하는 1을 더하면 이 문제의 답이 나온다. 여기서 특정 제곱수란 j에 어떤 제곱수를 더하여 i를 만드는 그 '어떤 제곱수'를 말한다.

 

예를 들어서 14를 만들고자 할때 14보다 낮은 정수에 제곱수를 하나 더하여 14를 만들 수 있는 경우는

13+1^2, 10+2^2, 5+3^2 이렇게 3가지 경우가 있다.

14를 제곱수의 합으로 표현 할 수 있는 항의 최소개수를 구하려면 13, 10, 5를 각각 제곱수의 합으로 표현 할 때, 그 항의 최소개수들의 최솟값에 1을 더하면 된다. 13,10,5을 각각 제곱수들의 합으로 표현하려면 모두 2개씩의 제곱수만 필요하므로, 이 경우에는 그냥 2에 1을 더해준 3이 14의 dp값이 된다.

여기서 1을 더한다는 것은 특정 제곱수를 하나 더하여 14를 만들었다는 의미다.

 

이 사실을 적용하여 1부터 dp를 수행하면 아래와 같은 표가 만들어진다. 15까지 만들어보았다.

dp값은 각 int값을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <stack>
using namespace std;
int min(int a, int b){ return a < b ? a : b; }
int dy[100001];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i <= n; i++) dy[i] = i;
	for (int i = 2; i <= n; i++)
		for (int j = 2; j*j <= i; j++)
			dy[i] = min(dy[i], dy[i - j*j] + 1);			
	cout << dy[n];
}