[BOJ] 2470 : 두 용액

문제 링크

2470번: 두 용액 (acmicpc.net)

2470번: 두 용액

풀이

두 용액의 특성값의 합이 0에 가장 가까운 용액을 만드는 문제.

브루트포스로 해결하려 한다면 O(N^2) 이기때문에 당연히 시간초과가 난다.

투포인트 기법을 사용해야하는데 말 그대로 그냥 두 개의 점을 찍는 방식이다.

먼저 용액의 특성값들이 담긴 벡터를 오름차순으로 정렬한다.

Left를 0 Right를 N-1로 잡고(Left와 Right가 두 점이 된다)

벡터의 Left 인덱스와 Right인덱스에 있는 값의 합을 구한다.

만약 합이 양수라면 합을 줄여야 하기 때문에 Right 값을 줄인다.

반대로 합이 음수라면 합을 늘려야 하기 때문에 Left값을 늘린다.

이렇게 해서 최소인 지점을 찾으면 끝.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef priority_queue <pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
int N;
ll Min = LLONG_MAX;
vector<int> v;
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    int L = 0;
    int R = v.size() - 1;
    int ans1, ans2;
    while (L < R) {
        if (abs(v[L] + v[R]) < Min) {
            ans1 = v[L];
            ans2 = v[R];
            Min = abs(v[L] + v[R]);
        }
        if (v[L] + v[R] > 0) {
            R--;
        }
        else {
            L++;
        }
    }
    cout << ans1 << " " << ans2 << "\n";
    return 0;
}

많은 사람들이 이분탐색으로 풀었다고 해서 이분탐색으로 하다가 시간을 많이 잡아먹었다.