[백준] #2470 두 용액

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

2470번: 두 용액

 

알고리즘 분류는 이진탐색으로 되어있지만, 그냥 투포인트 방식으로도 풀리는 문제였다. 오히려 그게 시간 효율이 더 좋을수도..?

---

• 풀이

알고리즘은 간단하다. int형 벡터에 숫자를 입력받아서 오름차순로 정렬해주고, 왼쪽 끝과 오른쪽 끝 이렇게 두 포인터를 이동시키며 가장 0에 가까운 값이 될때까지 포인터들을 갱신해주면 된다.

---

• 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int toAbsoluteValue(int a) {
    if (a < 0) return -a;
    return a;
}

int main(void) {
    int N;
    cin >> N;

    vector<int> v;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());

    int left = 0, right = N-1, total = v[left] + v[right];
    int tmpL = 0, tmpR = N-1, tmpTotal;

    while (tmpL < tmpR) {
        tmpTotal = v[tmpL] + v[tmpR];

        if (toAbsoluteValue(tmpTotal) < toAbsoluteValue(total)) {
            total = tmpTotal;
            left = tmpL;
            right = tmpR;
        }

        if (tmpTotal <= 0) tmpL++;
        else tmpR--;
    }
    cout << v[left] << " " << v[right];

    return 0;
}

---