문제 링크

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

사용 언어

C++

소스

#include <iostream>
#include <algorithm>
#define abs(x) (((x)<0)?((-1)*(x)):(x))
using namespace std;
  
int N;
int A[100000];
int Min = ~(1 << 31);
  
bool compare(int a, int b){
	return abs(a) < abs(b);
}
  
int main()
{
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	sort(A, A+N, compare);
	for(int i = 1; i < N; i++){
		int x = A[i-1]+A[i];
		if(abs(x) < abs(Min)) Min = x;
	}
	cout << Min;
}

논리

만약 모든 원소의 쌍의 합을 조사한다면, 시간 복잡도는 O(N²)이 된다.

그리고 이러한 알고리즘은 시간초과 에러를 띄우게 된다.

더 좋은 알고리즘은 다음과 같다.

{A_i}를 절댓값 기준으로 정렬한 후, 각 이웃끼리 합의 절댓값의 최솟값을 찾는다.

어떻게 절댓값 기준으로 정렬된 배열의 이웃에서 최솟값이 발생할 것이라고 보장할 수 있는가.

증명과정을 보이도록 하겠다.

• def

  {C_i} = c₁, c₂, …, c_n ({A_i}를 절댓값 기준으로 오름차순 정렬한 배열)

• claim

  \[\exists c_i, c_j \quad s.t \quad |c_i + c_j| \mbox{ is minimum} \quad \Rightarrow \quad |i-j|=1\]

• proof

  귀류법을 통해 증명하기 위해 다음과 같이 결론을 부정해본다.

  \[|c_i + c_j| \mbox{ is minimum} \quad \land \quad |i - j| > 1\]

  특히 일반성을 잃지 않고 \(i < j\) 라고 둘 수 있다.

  
  

  그런데 다음 3가지 중 적어도 하나는 참이다.

  1. \[c_i * c_j > 0 \quad \land \quad [\; \exists c_k \quad s.t \quad i < k < j \quad \land \quad c_i * c_k > 0 \;]\]
  2. \[c_i * c_j > 0 \quad \land \quad [\; \exists c_k \quad s.t \quad i < k < j \quad \land \quad c_i * c_k < 0 \;]\]
  3. \[c_i * c_j < 0\]

  그러면 어떤 경우라도 가정에 모순이 생긴다. 그 이유를 보이겠다.

  
  

  1. 다음 사실을 활용하자.

     \[xy \ge 0 \quad \Rightarrow \quad |x+y| =|x| + |y|\]

     그러면

     \[\left| c_i + c_j\right|=\left| c_i \right| + \left| c_k \right| < \left| c_i \right| + \left| c_j \right| = \left| c_i + c_j \right|\]

     이므로 모순

  2. 삼각부등식을 활용하자.

     \[|x+y| \le |x| + |y|\]

     그러면

     \[\begin{cases} |c_i + c_k| \le |c_i| + |c_k| \\\\ |c_i + c_j| \le |c_i| + |c_j| \end{cases}\]

     이다.

     \[\therefore |c_i + c_k| \le |c_i| + |c_k| < |c_i| + |c_j| = |c_i + c_j|\]

     따라서 모순.

  3. 다음 사실을 활용하자.

     \[\forall c_k(i<k<j), \quad c_i * c_k < 0 \quad \lor \quad c_k * c_j < 0\]

     일반성을 잃지 않고, \(c_i * c_k < 0\) 이라고 가정할 수 있다.
     

     \[xy < 0 \quad \Rightarrow \quad |x + y| = ||x| - |y||\]

     임을 활용하자.
     

     특히

     \[|c_i| < |c_k| < |c_j|\]

     이고,

     \[\begin{cases} |c_i + c_k| = |c_k| - |c_i|\\ |c_i + c_j| = |c_j| - |c_i| \end{cases}\]

     이므로

     \[\therefore |c_i + c_k| = |c_k| - |c_i| < |c_j| - |c_i| = |c_i + c_j|\]

     즉, 모순이다.

     결국 모든 경우에 대해 모순을 보였으므로, 증명이 완료 된다.

그래서 위와 같은 알고리즘으로 최솟값을 찾아낼 수 있다.

시간 복잡도는 배열을 정렬하는데 O(NlogN)이 걸리고,

정렬된 배열에서 최소값을 찾는데는 O(N)이 걸리므로 O(NlogN) + O(N) = O(NlogN)이 걸린다.