제곱수의 합 (feat. 백준, 1699번)

제곱수의 합
https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1699
#include <iostream>
#include <cmath>
using namespace std;
int N, dp[100001];
int solution(int n) {
	if (dp[n] == 0) {
		dp[n] = static_cast<int>(1e9);
		for (register int i = static_cast<int>(sqrt(n)), x; i >= 1; --i)
			x = static_cast<int>(pow(i, 2)), dp[n] = min(solution(n - x) + 1, dp[n]);
	}
	return dp[n];
}
int main() {
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		dp[i] = 0;
	for (register int i = 1; i * i <= N; ++i)
		dp[i * i] = 1;
	cout << solution(N) << endl;
	return 0;
}
// *&)*@*

정답과 가장 가까운 제곱근부터 구하는 것에서 멈추지 않고, 그보다 작은 제곱근으로도 결과가 나오는지 확인하고 나온다면 항의 최소개수를 변경 해주어야 합니다.