[백준] BOJ_2473 세 용액

이종찬·2026년 1월 12일

baekjoon

1. 문제 정보

문제 요약: 산성(양수)과 알칼리성(음수) 특성을 가진 개의 용액이 주어집니다. 이 중 서로 다른 세 개의 용액을 혼합하여, 그 특성값의 합이 0에 가장 가까운 조합을 찾아내야 합니다.
핵심 제약 조건:
용액의 수 : 용액의 수 $N$ : $3 \le N \le 5,000$
용액의 특성값: $-1,000,000,000 \le \text{Value} \le 1,000,000,000$ (int 범위를 넘을 수 있음)
난이도: Gold 3
원본 링크: https://www.acmicpc.net/problem/2473

2. 접근 방식

문제를 보자마자 바로 코드를 치기보다, 입력 크기를 보고 어떤 알고리즘이 "가능한지" 먼저 판단해야 합니다.

1) 문제의 본질

우리가 풀어야 할 문제는 개의 숫자 중 3개를 뽑아 합을 구하는 것입니다. 가장 직관적인 방법은 3중 반복문(또는 재귀를 이용한 조합)을 사용하는 것입니다.

완전 탐색(Brute Force) 시도 시:
$N$ 개 중 3개를 뽑는 경우의 수는 ${}_N \mathrm{C}_3$ 입니다.
계산해 보면 $\frac{N(N-1)(N-2)}{6} \approx \frac{N^3}{6}$ 입니다.
$N=5,000$ 일 때, $5000^3 = 125,000,000,000$ (1,250억) 번의 연산이 필요합니다.
통상적으로 1초에 약 1억( $10^8$ ) 번의 연산을 처리한다고 가정할 때, 이는 시간 초과(TLE)가 확정적입니다.

2) 알고리즘 설계

3개의 변수를 동시에 컨트롤하는 것은 복잡합니다. 변수 하나를 고정(Fixing)하여 문제를 단순화시켜 봅시다.

정렬(Sorting): 투 포인터나 이분 탐색을 사용하기 위해 데이터를 오름차순으로 정렬합니다.
하나 고정(Linear Scan): 첫 번째 용액을 배열의 $i$ 번째 요소로 고정합니다. ( $0 \le i \le N-3$ )
투 포인터(Two Pointers): 나머지 두 용액을 찾기 위해 $i+1$ 부터 $N-1$ 구간에서 투 포인터를 수행합니다.

left는 $i+1$ (가장 작은 값 쪽), right는 $N-1$ (가장 큰 값 쪽)에 둡니다.
세 용액의 합이 0보다 크다면, 값을 줄여야 하므로 right를 왼쪽으로 이동합니다.
세 용액의 합이 0보다 작다면, 값을 키워야 하므로 left를 오른쪽으로 이동합니다.

이 방식을 사용하면, 첫 번째 용액을 고정하는 루프( $N$ ) $\times$ 투 포인터 탐색( $N$ ) = $O(N^2)$ 시간 복잡도로 해결이 가능합니다.

3) 점화식 및 수식

현재 검사 중인 세 용액의 합을 라고 할 때, 갱신 로직은 다음과 같습니다.
$S = A[i] + A[\text{left}] + A[\text{right}]$

$S > 0$ : $\text{right} \leftarrow \text{right} - 1$
$S < 0$ : $\text{left} \leftarrow \text{left} + 1$
$S = 0$ : 최적해이므로 즉시 종료 및 출력.

3. 코드 구현

1) 실패한 코드 (시간 초과)

처음에 시도하신 재귀(백트래킹) 방식입니다. 로직 자체는 틀리지 않았으나, $N=5000$ 이라는 제약 조건 앞에서 $O(N^3)$ 의 벽을 넘지 못했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static long[] A;
    static long answer = Long.MAX_VALUE;
    static long[] result;
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        A = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(A);
        result = new long[3];
        // 문제점: N=5000일 때 3중 for문(재귀)은 약 200억 번 이상의 연산을 수행하여 시간 초과 발생
        for (int i = 0; i <= N / 2; i++) {
            recursion(i, 1, new long[]{A[i], INF, INF});
        }

        StringBuilder sb = new StringBuilder();
        for (long n : result)
            sb.append(n).append(' ');
        System.out.println(sb);
    }

    private static void recursion(int start, int count, long[] tmp) {
        if (count == 3) {
            long sum = tmp[0] + tmp[1] + tmp[2];
            if (Math.abs(answer) > Math.abs(sum)) {
                answer = sum;
                result = tmp.clone();
            }
            return;
        }

        for (int i = start + 1; i < N; i++) {
            tmp[count] = A[i];
            recursion(i, count + 1, tmp);
            tmp[count] = INF;
        }
    }
}

2) 성공한 코드

하나를 고정하고 나머지 둘을 투 포인터로 찾는 $O(N^2)$ 방식의 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static long[] A;
    static long answer = Long.MAX_VALUE;
    static long[] result;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        A = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        // 투 포인터 활용을 위한 필수 전처리: 정렬
        Arrays.sort(A);

        result = new long[3];
        // 첫 번째 용액을 고정 (i)
        for (int i = 0; i < N - 2; i++) {
            solv(i);
        }

        StringBuilder sb = new StringBuilder();
        for (long n : result)
            sb.append(n).append(' ');
        System.out.println(sb);
    }

    // 고정된 idx에 대해 나머지 두 용액을 투 포인터로 탐색
    private static void solv(int idx) {
        int left = idx + 1; // 고정된 값 바로 다음부터 시작
        int right = N - 1;  // 배열의 끝에서 시작

        while (left < right) {
            long sum = A[idx] + A[left] + A[right];

            // 0에 더 가까운 값을 찾으면 갱신
            if (Math.abs(answer) > Math.abs(sum)) {
                answer = sum;
                result[0] = A[idx];
                result[1] = A[left];
                result[2] = A[right];
            }

            // 합이 0보다 크면 줄여야 하므로 right 이동
            if (sum > 0) {
                right -= 1;
            } 
            // 합이 0보다 작으면 키워야 하므로 left 이동
            else {
                left += 1;
            }
        }
    }
}

4. 회고 및 배운 점

이번 문제를 통해 시간 복잡도 분석의 중요성을 다시 한번 체감했습니다.

시간 복잡도 비교 ( $O(N^3)$ vs $O(N^2)$ ):

실패 코드는 재귀를 통한 조합 탐색으로 $O(N^3)$ 에 가까운 시간이 소요되었습니다. $N=5,000$ 일 때 이는 계산 불가능한 영역입니다.
성공 코드는 for문 하나( $N$ )와 그 내부의 while문(투 포인터, $N$ )이 결합되어 $O(N^2)$ 입니다. $5,000^2 = 25,000,000$ 회 연산이므로 1초(약 1억 회) 안에 충분히 넉넉하게 동작합니다.

데이터 타입 주의 (Overflow):

문제에서 각 용액의 값은 최대 $10^9$ 입니다. 세 용액의 합은 최대 $3 \times 10^9$ 가 될 수 있습니다.
Java의 int형 최대값은 약 $2.1 \times 10^9$ 이므로, 합을 계산할 때 반드시 long 타입을 사용해야 합니다. 코드에서 sum 변수와 A 배열을 long으로 선언하여 오버플로우를 잘 방지했습니다.