백준 2470 두 용액

절대값 기준으로 정렬 후

이웃한 두 수 끼리만 더해서

제일 합이 작은 쌍을 출력하면 됨

절대값 기준으로 정렬하여 '이웃 끼리의 숫자만 확인하면 된다' 가 정답인 이유는 아래와 같다

만약 이웃끼리 붙은 숫자 쌍이 정답이 아닐 경우를 생각해보자

A B C D ..... 와 같은 수가 있을때

B와 D의 합이 B와 C의 합 혹은 C와 D의 합보다 절대값이 더 작다는 뜻을 의미한다.

한편 B, C, D는 아래와 같은 경우의 수가 있을 수 있다.

1. B C D 순서대로 음수, 음수, 음수 or 양수, 양수, 양수 와 같이 세 수 모두 부호가 같을 경우

2. B와 D가 다른 부호일 경우(음양양, 음음양, 양양음, 양음음)

3. B와 D가 같은 부호인데 C만 다를 경우(양음양, 음양음)

1번의 경우, B와 D의 합이 정답이 아닌것은 자명하다. (오름차순이거나 내림차순이기 때문)

3번의 경우, 음수와 음수를 더하거나 양수와 양수를 더하면 절대값이 더 커지는데, 중간에 있는 부호가 다른 수를 더하면 절대값이 작아지는 것 또한 자명하다.

2번의 경우, 

부호가 다른 숫자는 부호가 같은 두개의 숫자중 자기와 거리가 더 가까운 것과 합하여야 한다.

2.1. 음양양의 경우 : B와 C의 합이 B와 D의 합보다 절대값이 더 작다

2.2. 음음양의 경우 : C와 D의 합이 B와 D의 합보다 절대값이 더 작다

2.3. 양양음의 경우 : C와 D의 합이 B와 D의 합보다 절대값이 더 작다

2.4. 양음음의 경우 : B와 C의 합이 B와 D의 합보다 절대값이 더 작다

따라서 절대값으로 정렬하여 이웃한 수끼리만 보면 된다.

#include <iostream>
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>
#include <functional>
 
using namespace std;

int N;
vector<long long> arr;

bool compare(long long a, long long b) {
	return abs(a) < abs(b);
}

int main() {
	int temp, minA = 100001, minB = 100001;
	long long min = 2100000000;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &temp);
		arr.push_back(temp);
	}
	sort(arr.begin(), arr.end(), compare);


	for (int i = 0; i < N - 1; i++) {
		if (abs(arr[i] + arr[i + 1]) < min) {
			min = abs(arr[i] + arr[i + 1]);
			minA = arr[i];
			minB = arr[i + 1];
		}
	}

	if(minA < minB) printf("%d %d", minA, minB);
	else printf("%d %d", minB, minA);

	return 0;
}