BOJ 2467번: 용액

문제 설명

두 용액을 혼합할 때, 전체 용액의 특성값이 0에 가장 가까운 조합을 구하기

🔗 문제 링크

핵심 아이디어

• 용액은 정렬된 상태로 주어짐
• 두 용액의 합이 0에 가까워야 함 → 투 포인터 (Two Pointers) 사용
• 정렬된 배열에서 왼쪽은 음수 쪽, 오른쪽은 양수 쪽 → 점차 좁혀가며 탐색
• 현재 합의 절댓값이 이전보다 작으면 정답 갱신

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
int arr[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    int left = 0;
    int right = n-1;
    
    ll best_sum = 1e18;
    int ans_left = 0, ans_right = n - 1;
    
    while(left < right){
        ll sum = arr[left] + arr[right];
        
        if (abs(sum) < best_sum) {
            best_sum = abs(sum);
            ans_left = left;
            ans_right = right;
        }
        
        if (sum < 0) left++;
        else right--;
    }
    cout << arr[ans_left] << ' ' << arr[ans_right];
}

‼️ 놓친 점

• arr[left]와 arr[right]의 합이 0보다 작으면, 더 큰 값을 시도해야 하므로 left++
• 반대로 합이 0보다 크면, 더 작은 값을 시도해야 하므로 right--
• 현재 합이 더 0에 가까우면 바로 정답 후보 갱신
• 배열이 이미 정렬되어 있다는 점을 이용하여 O(N) 시간에 해결 가능 (Brute force N²은 시간 초과)