[C++] 백준 17626번: Four Sqaures

규칙을 찾던 과정이다

문제 바로가기

⚽문제가 무엇일까?⚽

1 ≤ N ≤ 50,000인 자연수 N이 입력되면, 이 수를 제곱수의 합으로 나타낼 수 있다.

라그랑주는 모든 자연수를 4개 이하의 제곱수 합으로 표현할 수 있음을 증명했다.

어떤 자연수를 제곱수의 합으로 나타내는 여러가지일 수 있다.

우리는 주어진 자연수 N을 제곱수의 합으로 나타낼 때, 그 개수의 최소값을 찾는게 목표다.

 

⚾어떻게 풀지?⚾

위 사진처럼 차근차근 적어봐도, 규칙성을 찾기란 어렵다. 그래서 단순하게 생각했다.

N 이하의 제곱수 중 가장 큰 수부터 연산을 하는 것이다.

예로, N이 8이면 4 두 번으로 표현이 된다.

하지만, 이렇게 설계하고 예제를 돌려보면 다른 답이 나온다.

가장 큰 제곱수가 항상 옳은 선택은 아니라는 뜻이다.

따라서, 이를 상한선을 낮춰가며 연산을 끝까지 반복하여 그 중 최소를 찾는 방법을 선택했다.

#include <iostream>
#include <stack>

using namespace std;

#define EL "\n"
#define INF 987654321

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

	int N;
	cin >> N;

	stack<int> powers;
	for(int i = 1; i <= 223; i++)
		powers.push(i * i);

	int minCount = INF;
	while (powers.size()) {
		int K = N;
		int count = 0;
		stack<int> _powers = powers;

		while (_powers.size() && K > 0) {
			while (_powers.top() > K) {
				_powers.pop();
			}

			while (K >= _powers.top()) {
				K -= _powers.top();
				count++;
			}

			_powers.pop();
		}

		if (count < minCount)
			minCount = count;

		powers.pop();
	}

	cout << minCount << EL;

	return 0;
}

 

🥎결과는?🥎

틀렸습니다.

대부분의 경우에서 정답을 출력했지만, 70% 언저리에서 틀린 답을 내놓았다.

애초에 큰 수 순서대로 덧셈에 포함해 나가는게 모든 경우를 고려한게 아닐 뿐더러 그게 최소의 개수를 보장하지 않는다. 그 이유 때문에 큰 값을 내치면서 하고있지 않은가.

 

🏀다른 방법🏀

이 문제가 실버5 레이팅인 사실을 확인하고 다시 침착하게 생각해보자.

50,000이하의 제곱수는 223개다. 이 중 중복조합으로 4개를 선택하는 경우는 \(_{223}H_{4}=_{226}C_{4}=105,835,800\)이다. 컴퓨터로는 금방 계산한다. 심지어 중복조합으로 3개를 선택하는 경우만 고려하면 되는데, 왜냐하면 문제에서 주어진대로 모든 자연수는 최대 4개의 제곱수로 표현되기 때문이다.

따라서 우리가 필요한 연산은 

$$_{223}H_{3}+_{223}H_{2}+_{223}H_{1}=_{225}C_{3}+_{224}C_{2}+_{223}C_{1}=1,898,399$$

놀랍게도 주먹구구식으로 풀어도 문제없다.

 

🎈정답 코드🎈

#include <iostream>
#include <vector>

using namespace std;

#define EL "\n"

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

	int N;
	cin >> N;

	vector<int> powers;
	for(int i = 1; i <= 223; i++)
		powers.push_back(i * i);

	int count = 4;
	for (int& p : powers)
		if (p == N) {
			count = 1;
			goto END;
		}

	for (int& p1 : powers)
		for (int& p2 : powers)
			if (p1 + p2 == N) {
				count = 2;
				goto END;
			}

	for (int& p1 : powers)
		for (int& p2 : powers)
			for(int& p3 : powers)
				if (p1 + p2 + p3 == N) {
					count = 3;
					goto END;
				}

END:
	cout << count << EL;

	return 0;
}