<Baekjoon>#1699 제곱수의 합 (Sum of square number) c++

문제만 봐서는 아무런 아이디어도 떠오르지 않아서
표에 채워 넣어가면서 규칙을 찾아보려 했다.

여기서 얻었던 몇 개의 단서는
dp[1]=1
dp[i*i]=1 (어떤 수의 제곱 수는 1)

dp[3]=dp[3-1*1]+1
dp[5]=dp[5-2*2]+1
dp[6]=dp[6-2*2]+1
…

이런 규칙을 찾을 수 있다
(여기서 +1이란 1*1 의미가 아니라 1개를 의미한다)

하지만 항상 dp[N]에서 N보다 작은 가장 큰 제곱수를 뺀 값이 답은 아니다
e.g.
dp[43]=dp[43-6*6]+1=dp[7-2*2]+2=dp[3-1*1]+3=5

dp[43]=dp[43-5*5]+1=dp[18-3*3]+2=dp[9-3*3]+3=3

이 말은 반복문을 사용하여 dp[N]에서 N보다 작거나 같은 제곱수들을 하나씩 빼서 1을 더해주면서 가장 작은 값을 비교해 저장해야 한다.

참고로 dp[0]=0 으로 초기화 한다
(e.g. dp[9]=dp[9-3*3]+1=dp[0]+1 이런 경우 때문에)

1. Bottom-up 방식

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 100000;

int sqaureSum(int n) {
	vector<int>dp(n + 1, 0);

	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 );
		}
	}
	return dp[n];
}

int main() {
	int n;
	cin >> n;

	if (n > MAX)
		exit(EXIT_FAILURE);

	cout<<sqaureSum(n)<<endl;

	return 0;
}

2. Memoization 기법인 top-down 방식

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 100000;

int dp[MAX + 1];

int sqaureSum_(int n) {
	if (dp[n] != -1) return dp[n];
	dp[n] = n;
	for (int i = 1; i * i <= n; i++) {
		dp[n] = min(dp[n], sqaureSum_(n - (i * i)) + 1);
	}
	return dp[n];
}

int main() {
	int n;
	cin >> n;

	if (n > MAX)
		exit(EXIT_FAILURE);
	
	dp[0] = 0;
	for (int i = 1; i <= MAX; i++)
		dp[i] = -1;

	cout <<sqaureSum_(n) << endl;

	return 0;
}

top-down 이랑 bottom-up 방식의 메모리랑 시간 차이가 거의 2배나 났다.