[백준1699] 제곱수의 합 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int d[100001] = { 0 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	if (d[n] == 1) {
		cout << d[n];
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		d[i] = i;
		for (int j = 1; j * j <= i; j++) {
			d[i] = min(d[i], d[i - j * j] + 1);
		}
	}
	cout << d[n];
	return 0;
}

처음에 TOP-DOWN 방식으로 풀었는데 숫자가 너무 커서 그런지 스택 오버플로우가 발생하였다. 결국은 정답 소스코드를 참고하여 반복문을 이용한 방식으로 풀었다.

📌아이디어

다음의 점화식이 핵심이다. d[n]은 숫자 n을 제곱수의 합으로 나타냈을 때의 최소 길이를 의미한다.

d[n]=min(d[i],d[i-j*j]+1)

N은 n-i^2와 i^2의 합으로 나타낼 수 있다. 이 때 i^2는 하나의 항이기 때문에 d[n]은 d[n-i^2]에 1을 더한 값이 된다. dp 문제를 풀 때는 숫자를 잘게 분해하고 그를 통해 아이디어를 얻는 게 중요할 것 같다.

이전에 풀었던 1+2+3 더하기 문제와 유사하다.
[백준9095] 1, 2, 3 더해서 숫자를 표현하는 방법의 수 (C++)