[C++]BOJ 1699 - 제곱수의 합

만약 i라는 숫자보다 j * j만큼 작은 수 인 i - j * j는 숫자 i의 제곱수의 최소항 갯수 - 1을 가질 것이다.
만약 j * j가 i와 같다면 j * j = i이므로 제곱수의 최소항 갯수가 한개가 된다.
이 과정을 j * j가 i보다 작거나 같을 때까지 반복해 가장 작은 값을 dp[i]에 넣고 i가 n만큼 돌면 dp[n]이 답이 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, dp[100001];
int main() {
	cin >> n;
	for(int i = 0; i <= n; i++)
		dp[i] = i;
	for(int i = 2; i <= n; i++)
		for(int j = 2; j * j <= i; j++)
			dp[i] = min(dp[i - j * j] + 1, dp[i]);
	cout << dp[n];
}

구글링 하다가 동적 계획법 말고 다른 방법을 사용한 다른 풀이를 발견해서 첨부한다.
라그랑주의 네 제곱수 정리에 의하여 모든 양의 정수는 최대 4개의 제곱수의 합으로 나타낼 수 있기 때문에 3개의 제곱수의 합으로 못찾아내면 4개라는 점을 이용한 반쪽짜리 완전탐색 코드다.
3중 for문이라 되게 오래 걸릴 것 같지만 제곱근 n에 대하여 매우 빠르게 수가 불어나서 생각보다 빠르다.
오히려 dp보다 빠를 수도 있다.

#include <iostream>
using namespace std;
int n, ans = 4;
int main() {
	cin >> n;
	for(int a = 1; a * a <= n; a++) {
		if(a * a == n) ans = min(ans, 1);
		for(int b = 1; a * a + b * b <= n; b++) {
			if(a * a + b * b == n) ans = min(ans, 2);
			for(int c = 1; a * a + b * b + c * c <= n; c++)
				if(a * a + b * b + c * c == n) ans = min(ans, 3);
		}
	}
	cout << ans;
}

채첨 안해봐서 정답 처리 받을 수 있는지 모른다.
근데 잘 나온다.