문제

아이디어

가장 기초적인 풀이는 모든 조합을 구하는 완전 탐색이다.
하지만 N <= 100,000의 범위를 갖기 때문에 O(N^2)의 시간복잡도를 갖는 완전 탐색을 이용할 수 는 없을 것이다.
구체적으로는 최소한 O(NlogN)의 시간복잡도 이하의 풀이를 고려해야 한다.

그래도 완전 탐색을 이용하여 풀이한다고 가정하자.
그렇다면 임의의 시간에 혼합 용액 특성값의 최소 절댓값 min을 업데이트하는 방법은 아래와 같을 것이다.

1. 용액 A, B 를 선택해 혼합한다. A 용액은 a번, B 용액은 b번이라고 할 때, 조건은 아래와 같다.
   1 <= a < N, a < b <= N
2. 혼합 용액의 특성값과 현재의 최적해를 비교해 업데이트한다.

이 때, 새로운 혼합 용액의 특성값을 mix이라고 한다면 -min < max < min을 만족할 때, min의 업데이트가 발생한다. 더 자세히 알아보자면, 용액 A의 특성값을 ValueA, 용액 B의 특성값을 ValueB라고 한다면, mix = ValueA + ValueB이므로 ValueA - min < ValueB < ValueA + min일 때 업데이트가 발생한다.

굉장히 복잡한 수식들이 나왔지만 요점은 다음과 같다. 용액의 특성값들이 정렬되어 있다면 이분 탐색을 통해 min을 업데이트할 수 있는 ValueB를 구할 수 있다.

따라서 처음 주어지는 특성값들을 정렬한 후, 이분탐색을 통해 최적해를 업데이트한다면 O(NlogN)의 시간복잡도로 풀이할 수 있겠다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int min, left, right;
    static List<Integer> liq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        liq = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            liq.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(liq);

        min = Integer.MAX_VALUE;
        for (int i = 1; i < N; i++) {
            if (min > Math.abs(liq.get(0) + liq.get(i))) {
                min = Math.abs(liq.get(0) + liq.get(i));
                left = liq.get(0);
                right = liq.get(i);
            }
        }

        for (int i = 1; i < N; i++) {
            binSearch(i + 1, N - 1, liq.get(i));
        }

        System.out.println(left + " " + right);
    }

    static int mid, mix;

    public static void binSearch(int start, int end, int value) {

        while (start <= end) {
            mid = (start + end) / 2;
            mix = value + liq.get(mid);

            if (mix < -min) {
                start = mid + 1;
            } else if (mix > min) {
                end = mid - 1;
            } else {
                min = Math.abs(mix);
                left = value;
                right = liq.get(mid);

                if (mix < 0) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }
}

채점결과