[백준] [C++] 2473번 세 용액 (bsearch, two pointer)

1. 문제

2473번: 세 용액 (acmicpc.net)

2473번: 세 용액

 

2. 이진 탐색

일단 용액들을 정렬하고 난 뒤,

 

완전 탐색으로 두개의 용액을 합한다.

 

그리고 그 합과 합할 나머지 용액하나를 정렬된 배열에서

 

이진 탐색하는 방법으로 문제를 해결하였다.

 

총 수행시간은 O(N^2 lgN) 이 걸린다.

 

이 문제를 풀때 시도를 많이 했는데,

 

문제는 타입이였다. 이전 용액 문제에서는 두개의 용액으로, 합해도 20억이 넘지 않았지만

 

이 문제는 3개의 용액이므로 30억이 되어 int형으로는 오버플로우가 발생하게 된다.

 

코드는 다음과 같다.

lo 와 그리고 lo -1 을 검사하는 이유 lower bound 의 값이 만약 있을 경우 정확한 0이 된다. 만약 존재하지 않게되면 + 방향인 값이 주어지게 된다. - 방향의 절대값이 더 0과 가까울 수 있기 때문에 lo -1을 검사해야한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin>>N;
    vector<long long> s(N);
    long long answer = 3000000001;
 
    for(int i = 0; i < N; i++) {
        cin>>s[i];
    }
    sort(s.begin(), s.end());
 
    long long abc[3] = {s[0], s[1], s[2]};
 
    for(int i = 0; i < N; i++) {
       for(int j = i + 1; j < N; j++) {
           long long sum = s[i] + s[j];
           auto lo = lower_bound(s.begin() + j + 1, s.end(), -sum);
           int test[2] = {(int) (lo - s.begin()),
                          (int) (lo - 1 - s.begin())};
          
           for(int k = 0; k < 2; k++) {
               int idx = test[k];
               if(idx < 0 || idx >= N) {
                   continue;
               }
               if(answer > abs(sum + s[idx]) && idx != j) {
                   answer = abs(sum + s[idx]);
                   abc[0] = s[i];
                   abc[1] = s[j];
                   abc[2] = s[idx];
               }
           }
       }
    }
    
    sort(abc, abc + 3);
    
    std::cout<<abc[0]<<" "<<abc[1] << " " << abc[2];
}

 

3. two pointer, 양방향 탐색

백준 2473번 세 용액 (tistory.com)