[백준(BOJ)] 세 용액(2473번)_C++

세 용액의 합이기 때문에 일반적인 이분탐색으로는 해결할 수 없었다.

그래서 나는 처음에 이분탐색으로 진행하는데 start와 end 사이의 모든 용액에 대해 확인하는 방식으로 구현했다.

시간초과가 발생해서 원인을 찾아보려고 확인을 해봤다.

정답은 찾았는데 while문 안에 for문이 있기 때문에 while문을 탈출하기 까다로웠다.

 

다른 방법을 찾아본 결과 맨 왼쪽을 고정해놓고, 오른쪽 부분에서 투포인터를 사용하는 방법이 있었다.

이 방법은 for 문 안에 while문이 있어서 탈출하기 더 쉬웠다.

 

그래도 뭔가 이전에 했던 방법으로도 풀 수 있을 것 같아서 계속 시도해봐야겠다.

 

---

정답

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[5000];
long long sum = 3000000000;
int sol1, sol2, sol3;

void binary_search(){

    for(int fix = 0; fix < n - 2; fix++){
        int start = fix + 1;
        int end = n - 1;

        while (start < end){
            long long temp_sum = (long long)arr[fix] + arr[start] + arr[end];

            if (abs(temp_sum) < abs(sum)){
                sol1 = arr[fix];
                sol2 = arr[start];
                sol3 = arr[end];

                sum = temp_sum;
            }

            if (temp_sum >= 0)
                end--;
            else
                start++;
        }
    }
}

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

    //input
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    //sort
    sort(arr, arr + n);

    //binary search
    binary_search();

    //output
    cout << sol1 << " " << sol2 << " " << sol3;
}