취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2007번 문제인 수들의 합 3이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2007 

N=2인 경우, 주어지는 수를 x라 할 때 x-10,000,000과 10,000,000을 두 수로 제시하는 것으로 문제를 해결할 수 있다. 아래에서는 N이 3 이상이라 가정하자.

찾아야 할 N개의 수 중 가장 작은 세 수를 a, b, c라 하자. 만약 a+b, a+c, b+c 세 값을 알 수 있다면 a, b, c의 값 또한 자연스레 계산할 수 있게 된다. 가장 작은 수 a를 알고 있다면 주어진 두 수의 합들을 오름차순으로 살펴보면서 "지금까지 나온 수들의 합으로 만들어지지 않은 수"를 찾을 때마다 그 수를 "a와 새로운 수의 합"으로 생각하는 것으로 N개의 수를 찾아내 문제를 해결할 수 있을 것이다.

두 수들의 합 중 가장 작은 것은 a+b, 두번째로 가장 작은 것은 a+c와 값이 같다. a가 없는 N-1개의 수중 둘을 뽑아 합할 때의 최솟값이 b+c가 됨을 관찰하면, b+c보다 작은 값을 가질 수 있는 후보는 a+(N개의 수중 4~N번째로 작은 수)들 외에는 없다는 것을 알 수 있다. 따라서, b+c의 후보로 a+b, a+c 이후의 N - 2개의 수를 집어넣어 보는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int N, NN;
int arr[10000];

bool func(int a, int b, int c) {
	vector<int> vec;
	vec.emplace_back(a); vec.emplace_back(b); vec.emplace_back(c);
	map<int, int> mpmp;
	mpmp.insert(make_pair(a + b, 1));
	if (mpmp.count(a + c)) mpmp[a + c]++;
	else mpmp.insert(make_pair(a + c, 1));
	if (mpmp.count(b + c)) mpmp[b + c]++;
	else mpmp.insert(make_pair(b + c, 1));

	for (int i = 0; i < NN && vec.size() <= N; i++) {
		if (mpmp.count(arr[i]) && mpmp[arr[i]] > 0) mpmp[arr[i]]--;
		else {
			int nxt = arr[i] - a;
			for (auto& x : vec) {
				int cur = nxt + x;
				if (mpmp.count(cur)) mpmp[cur]++;
				else mpmp.insert(make_pair(cur, 1));
			}
			vec.emplace_back(nxt), mpmp[arr[i]]--;
		}
	}

	if (vec.size() == N) {
		sort(vec.begin(), vec.end());
		for (auto& x : vec) cout << x << ' ';
		return 1;
	}

	return 0;
}

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

	cin >> N;
	NN = N * (N - 1) / 2;
	for (int i = 0; i < NN; i++) cin >> arr[i];
	sort(arr, arr + NN);

	if (N == 2) {
		cout << -10000000 << ' ' << arr[0] + 10000000;
		return 0;
	}

	for (int i = 0; i < N && i + 2 < NN; i++) {
		int abc = arr[0] + arr[1] + arr[i + 2];
		if ((abc & 1) == 0) {
			abc /= 2;
			if (func(abc - arr[i + 2], abc - arr[1], abc - arr[0])) return 0;
		}
	}
	
	cout << "Impossible";
}