[백준] 2473번 : 세 용액

문제

 

---

풀이

 

https://myunji.tistory.com/362

[백준] 2470번 : 두 용액

이 문제를 응용한 것이다.

 

두 용액이면 투포인터를 쓰면 될 것인데 3개라 어떻게 할지 고민됐다.

근데 그냥 용액 하나를 고정하고 투포인터를 돌리면 되는 것이었다.

 

이렇게 초록색을 고정하고 빨간색과 파란색 포인터를 움직이자

N개의 용액이 있을때 초록색 포인터는 0~N-3번 용액까지 움직일 수 있다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>

using namespace std;
typedef long long ll;
const long long INF = 3 * 1e9 + 1;

vector<ll> liquid;
ll min_diff = INF;

pair<ll, ll> twoPointer(ll fixed, int left, int right) {
    pair<ll, ll> result;
    result = make_pair(INF, INF); //갱신이 안될 수도 있으므로 초기값 넣기
    while (left < right) { //둘의 위치가 역전되면 break
        ll sum = fixed + liquid[left] + liquid[right];
        if (sum == 0) //0이면 바로 리턴
            return make_pair(liquid[left], liquid[right]);
        if (abs(sum) < min_diff) { //최소 차이 갱신 가능한지 확인
            min_diff = abs(sum);
            result = make_pair(liquid[left], liquid[right]);
        }
        if (sum > 0) //0보다 크면 right 감소
            right--;
        else //0보다 작으면 left 증가
            left++;
    }
    return result;
}

int main() {
    int N;

    cin >> N;
    liquid.assign(N, 0);
    for (int i = 0; i < N; i++)
        cin >> liquid[i];
    sort(liquid.begin(), liquid.end()); //정렬
    tuple<ll, ll, ll> result;
    for (int i = 0; i < N - 2; i++) { //liquid[i]는 고정 용액
        pair<ll, ll> p = twoPointer(liquid[i], i + 1, N - 1);
        if ((p.first != INF) && (p.second != INF)) //최소 차이가 갱신됐으면 result 갱신
            result = make_tuple(liquid[i], p.first, p.second);
    }
    cout << get<0>(result) << ' ' << get<1>(result) << ' ' << get<2>(result);
}

전체 소스코드다.

 

    sort(liquid.begin(), liquid.end()); //정렬
    tuple<ll, ll, ll> result;
    for (int i = 0; i < N - 2; i++) { //liquid[i]는 고정 용액
        pair<ll, ll> p = twoPointer(liquid[i], i + 1, N - 1);
        if ((p.first != INF) && (p.second != INF)) //최소 차이가 갱신됐으면 result 갱신
            result = make_tuple(liquid[i], p.first, p.second);
    }

먼저 입력값을 정렬하고

0~N-3번 용액을 고정 용액으로 설정한 뒤 그 다음 인덱스를 left로 하고 마지막 용액을 right로 한 투포인터 알고리즘을 실행한다.

 

경우에 따라선 투포인터 알고리즘을 돌고나서도 최소 차이가 갱신되지 않을 때가 있을 것이다.

그럴땐 INF을 반환하도록 했으니 그렇지 않을 경우에만 result 튜플을 갱신한다.

 

pair<ll, ll> twoPointer(ll fixed, int left, int right) {
    pair<ll, ll> result;
    result = make_pair(INF, INF); //갱신이 안될 수도 있으므로 초기값 넣기
    while (left < right) { //둘의 위치가 역전되면 break
        ll sum = fixed + liquid[left] + liquid[right];
        if (sum == 0) //0이면 바로 리턴
            return make_pair(liquid[left], liquid[right]);
        if (abs(sum) < min_diff) { //최소 차이 갱신 가능한지 확인
            min_diff = abs(sum);
            result = make_pair(liquid[left], liquid[right]);
        }
        if (sum > 0) //0보다 크면 right 감소
            right--;
        else //0보다 작으면 left 증가
            left++;
    }
    return result;
}

2470번과 거의 동일한 코드인데

result의 초기값을 넣어주는 부분과 sum을 계산할 때 fixed를 함께 더해주는 부분을 추가했다.