[C++] BOJ / 1699번 / 제곱수의 합

1699번: 제곱수의 합

 

- 문제

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

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

 

- 입력

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

13

 

- 출력

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

2

---

#include <iostream>

using namespace std;

#define MAX 100000

int DP[MAX + 1];

int main()
{
	int n;

	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		DP[i] = i;
		for(int j = 1; j * j <= i; ++j)
			DP[i] = min(DP[i], DP[i - j * j] + 1);
	}

	cout << DP[n];
}

---

결과분석

처음에는 DP[i]를 i 까지의 숫자를 사용했을 경우 구할 수 있는 n의 제곱수 항의 최소 개수라고 정의하고 나름대로 풀이해보았으나 실패하고 구글링을 통해 풀이하였음.

 

본인이 찾은 블로그에서는 DP[i]를 어떤 수 i를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수로 정의한 뒤 i를 1부터 n까지 순차적으로 처리해나가면서 최종적으로 n의 제곱수 항의 최소 개수를 구하는 방식으로 풀이하였다고 함.

 

본인이 이해한 내용에 따르면 제곱수 j를 제곱하였을 때 n보다 크지 않다면 n은 j와 그 이하의 제곱수들의 합으로 나타낼 수 있다. 예를 들어 n이 5일 경우, j는 1과 2가 될 수 있다. 반복문 안에 있는 min(DP[i], DP[i - j * j] + 1)의 의미는 예를 들어보면 매우 쉽게 이해될 수 있을 것이다.

 

DP[5]의 경우를 생각해보면 min(DP[5], DP[5 - 1²] + 1), min(DP[5], DP[5 - 2²] + 1) 이렇게 두 경우가 있는데 여기서 DP[5 - 1²] 는 DP[4], 즉 자연수 4를 나타내는데 필요한 제곱수 항의 최소 개수를 의미한다. 4는 1² 을 더하면 바로 자연수 5가 될 수 있기 때문에 DP[4]에 1을 더한 값과 DP[5]의 값을 비교하여 더 작은 값을 DP[5]에 저장하는 식이다.

DP[5 - 2²] 또한 마찬가지로 DP[1], 즉 자연수 1을 나타내는데 필요한 제곱수 항의 최소 개수를 의미하며 1은 2²을 더하면 바로 자연수 5가 될 수 있기 때문에 DP[1]에 1을 더한 값과 DP[5]의 값을 비교하여 더 작은 값을 DP[5]에 저장하는 것이다. 즉 이런식으로 반복하다보면 최솟값이 계속해서 갱신될 것이며 최종적으로 우리가 얻고자 하는 n의 제곱수 항의 최소 개수를 구할 수 있는 것이다.