[BOJ / C++] 세 수의 합 (이분탐색)

문제링크: https://www.acmicpc.net/problem/2295

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    vector<int> two;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            two.push_back(arr[i] + arr[j]);
        }
    }
    sort(two.begin(), two.end());

    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (binary_search(two.begin(), two.end(), arr[i] - arr[j])) {
                cout << arr[i];
                return 0;
            }
        }
    }
}

 

 

2. 분석

만약 i, j, k를 다 더하고 이분탐색으로 찾으면 O(n^3lgn)이 되어 시간초과가 된다. 따라서 O(n^2lgn) 까지 시간복잡도를 낮춰야하는데 2개의 합을 미리 two 배열에 저장해두면 된다. 즉 arr[x] + arr[y] + arr[z] == arr[k]를 찾는 것이 아니라, arr[x] + arr[y] == arr[k] - arr[z]를 찾는 방식이다. 배열에서 선택은 중복돼도 상관없으므로 신경쓰지 않는다.

 

 

3. 시간복잡도

마지막 코드 부분에서 이중 for 문에 binary_search이므로 O(n^2lgn)이다. n = 10^3이므로 10^7 < 10^8 으로 시간제한 1초 내에 통과 가능하다.