백준 2473번, 한국정보올림피아드 2010년 고등부 1번, 세 용액 풀이

2020. 10. 10. 10:34Problem Solving/백준

문제

백준 2473번

풀이

가장 떠올리기 쉬운 풀이는 3개의 수의 조합을 찾아 모두 탐색하는 방법입니다.
3개의 조합을 뽑는 경우의 수가 $ _{n}C_{3} $이 될텐데 $ N $이 $ 5,000 $이니 TLE나기 좋은 시간복잡도입니다.


최적화를 해보겠습니다.
2개의 수(각각 $ A_{i}, A_{j} (i \neq j) $)를 뽑았을 때, 그리디하게 $ -(A_{i} + A_{j}) $와 가까운 수를 찾으면 0과 가까운 수를 만들 수 있습니다. 이 외의 나머지 수들은 답이 될 수 없습니다.

 

들어오는 수열을 정렬해놓고, $ -(A_{i} + A_{j}) $과 가까운 수를 이분 탐색을 사용하면 $ O(N^2logN) $에 풀 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    long long n, ans = 1e18;
    vector<long long> ans_comb;
    cin >> n;

    vector<long long> origin(n);
    for (int i = 0; i < n; i++) cin >> origin[i];

    sort(origin.begin(), origin.end());
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            long long sum = origin[i] + origin[j], tmp = 1e18;

            auto it = lower_bound(origin.begin(), origin.end(), -sum), sel = origin.begin();
            for (auto k = max(origin.begin(), it - 2); k <= it + 2 && k < origin.end(); k++) {
                if (*k != origin[i] && *k != origin[j]) {
                    if (tmp > abs(*k + sum)) {
                        tmp = abs(*k + sum);
                        sel = k;
                    }
                }
            }

            if (ans > tmp) {
                ans = tmp;
                ans_comb = {origin[i], origin[j], *sel};
            }
        }

    sort(ans_comb.begin(), ans_comb.end());
    for (const auto &v : ans_comb) cout << v << " ";
}