[백준/C++] 2473번 세 용액

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

2473번: 세 용액

2467번 용액, 2470번 두 용액, 2473번 세 용액으로 이어지는 시리즈 문제이다.

전체적인 맥락은 비슷하므로 한 문제만 포스팅하겠다. 

 

투포인터, 이분탐색의 활용문제이다. 총 3개의 포인터가 필요한데 약간의 테크닉이 필요하다.

우선 개략적인 방법은 흔한 투포인터를 이용한 이분탐색과 동일하다. 여기에 하나의 포인터를 추가하는데,

포인터 하나를 고정해서 이용한다!

 

맨 앞을 고정 포인터로 두고, 그 다음을 왼쪽 포인터, 그리고 배열의 끝을 오른쪽 포인터로 두며

맨 앞의 고정 포인터를 제외하고 나머지 두 포인터를 이분탐색하며 답을 찾아낸다. 이렇게 되면 자연스레 오름차순으로 출력도 가능하며, 쉽게 풀 수 있다.

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

vector<ll> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n;
    cin >> n;

    for (ll i = 0; i < n; i++) {
        ll num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    ll cmp = 3e9 + 1;

    ll first = 0;
    ll second = 0;
    ll third = 0;

    for (ll i = 0; i < n-2; i++) {
        ll start = i+1;
        ll end = n - 1;
        while (start < end) { // start >= end가 되면 종료
            ll buf = v[start] + v[end] + v[i];

            if (abs(buf) < cmp) {
                first = v[i];
                second = v[start];
                third = v[end];
                cmp = abs(buf);
            }
            if (buf < 0) start++; // 0보다 작으면 음수 한단계 키워줌
            else end--; // 0보다 크면 양수 한단계 줄여줌
        }
    }
    cout << first << ' ' << second << ' '<< third;
    return 0;
}