[이분 탐색] BOJ 2295 세 수의 합

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

 

 

2295번: 세 수의 합

 

문제 해결 알고리즘

 

$a_1 + a_2 + a_3 = a_4$ 이렇게 구하려고하면 $O(n^4)$의 시간복잡도가 나오기 때문에 시간초과가 발생한다.

 

그렇기 때문에

 

$a_1 + a_2 = a_4 - a_3$로 두 항의 값이 같은 걸 구하기 위해 이분 탐색을 하면 $O(n^2 \log n)$으로 해야 정답을 받는다.

 

 

소스 코드

 

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

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

    vector<int> v(N);
    vector<int> v_1;
    int result = 0;

    for(int i=0;i<N;i++){
        cin >> v[i];
    }
    
    // a_1 + a_2
    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            v_1.push_back(v[i] + v[j]);
        }
    }

    sort(v_1.begin(), v_1.end());

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(binary_search(v_1.begin(), v_1.end(), v[j] - v[i])) result = max(result, v[j]);
        }
    }

    cout << result;
}

 

메모

 

#include <algorithm> 헤더 사용

binary_search 함수를 사용해야한다. 훨씬 편함