[백준] 1699번. 제곱수의 합

[백준] 1699번. 제곱수의 합

1. 문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

3. 출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

4. 풀이

• 배열을 만들고 제곱수는 모두 값을 1로 초기화한다.
• 해당 수를 만들 수 있는 최소 경우의 수를 찾는다. (d[n] = min(d[n-1] + d[1], d[n-4] + d[4], d[n-3] + d[3]......)

5. 처음 코드와 달라진 점

• 젤 처음에는 제곱 수인지 찾는 함수를 구현하여 loop가 돌 때마다 제곱 수인지 확인했다.
• 저번 문제 풀 때는 j<=i/2까지 loop를 돌려놓고 멍청하게 j<i-1까지 loop를 돌렸다.
• 기본 로직은 크게 다르지 않았는데 시간 초과가 나서 조금씩 바꾸니까 굉장히 느리게 통과했다.

6. 코드

#include <iostream>
using namespace std;

int d[100001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	for (int i = 1; i * i <= n; i++) {
		d[i * i] = 1;
	}
	d[2] = 2;
	for (int i = 3; i <= n; i++) {
		if (d[i] == 1) continue;
		d[i] = d[i - 1] + 1;
		for (int j = 2; j <= i / 2; j++) {
			int value = d[i - j] + d[j];
			if (d[i] > value) d[i] = value;
		}
	}
	cout << d[n];
}