[BOJ/C++] 2295 - 세수의 합

문제

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

2295번: 세 수의 합

풀이

가장 처음에 생각난 풀이는 n^3 * logn의 풀이인데 (임의의 세수 합을 구해서 이분탐색으로 찾기) n 이 최대 1000이기 때문에 시간초과가 난다.

정답을 구하기 위해서는 n^2 또는 n^2logn의 풀이를 생각해야 했고 a + b + c = k 라고 할 때 a + b의 값을 갖는 배열을 만들기로 했다. a + b 배열을 만든 뒤 k - c가 a + b 배열 안에 있는지 이분탐색을 통해 확인하면 n^2logn만에 풀 수 있다.

코드

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

int arr[1000];
int n;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    vector<int> v;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            v.push_back(arr[i] + arr[j]);
        }
    }
    sort(v.begin(), v.end());
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 0; j < n; j++) {
            int k = arr[i] - arr[j];
            int st = 0, ed = v.size() - 1;
            while (st <= ed) {
                int mid = (st + ed) / 2;
                if (v[mid] == k) {
                    cout << arr[i];
                    return 0;
                } else if (v[mid] < k) {
                    st = mid + 1;
                } else {
                    ed = mid - 1;
                }
            }
        }
    }
}