[백준] 1699번 | 제곱수의 합 | C++

---

문제 링크: https://www.acmicpc.net/problem/1699

---

문제

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

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

---

입력

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

---

출력

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

---

내 풀이

모든 수를 제곱수의 합으로 표현하는 것이 목표다. 이때 합으로 표현할 때 사용하는 제곱수도 또 다른 제곱수의 합이 되므로 다이나믹프로그래밍을 사용했다.

---

코드

#include<iostream>

int N, f[100001];

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

int main() {
	scanf("%d", &N);

	f[1] = 1;	f[2] = 2;	f[3] = 3;	f[4] = 1;
	for (int n = 5; n <= N; n++) {
		f[n] = n;
		for (int t = 2; t*t <= n; t++) {
			f[n] = min(f[n], f[n - t*t] + 1);
		}
	}

	printf("%d", f[N]);

	return 0;
}