백준 1699번: 제곱수의 합

[문제 링크]

1699번: 제곱수의 합

---

간단한 dp 문제였다.

 

자연수 N을 제곱수의 합으로 나타낼 때 최소항의 개수를 찾는 방법은 min(1 + [N - (제곱한 값이 N보다 작거나 같은 수들의 제곱수)]의 항의 개수) 이다.

 

예를 들어 N = 10 일 때 최소 항의 개수는 dp[10] = min( 1 + dp[10-1], 1 + dp[10-4], 1 + dp[10-9] ) 로 나타낼 수 있다.

따라서 점화식은 다음과 같다.

for(i = 1; i<=N; i++)

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

---

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[100001];

int min(int a, int b) { return a < b ? a : b; }

int Topdown(int N)
{
	if (N == 0) return 0;

	int& ret = memo[N];
	if (ret != 0) return ret;

	ret = INF;

	for (int i = 1; i <= N; i++)
	{
		if (i*i > N) break;
		ret = min(ret, 1 + Topdown(N - i * i));
	}

	return ret;
}

int Bottomup(int N)
{
	memo[0] = 0;
	memo[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		memo[i] = INF;
		for (int j = 1; j <= N; j++)
		{
			if (j*j > i) break;
			memo[i] = min(memo[i], 1 + memo[i - j * j]);
		}
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;

	cout << "top-down: " << Topdown(N) << endl;
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 78 day