백준 2473번, 한국정보올림피아드 2010년 고등부 1번, 세 용액 풀이
2020. 10. 10. 10:34ㆍProblem Solving/백준
문제
풀이
가장 떠올리기 쉬운 풀이는 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 << " ";
}
'Problem Solving > 백준' 카테고리의 다른 글
백준 1226번, BOI 2008 4번, 국회 풀이 (0) | 2020.10.12 |
---|---|
백준 14867번, 한국정보올림피아드 2017년 고등부 1번, 물통 풀이 (0) | 2020.10.11 |
백준 11985번, 오렌지 출하 풀이 (0) | 2020.10.09 |
백준 2098번, 외판원 순회 풀이 (1) | 2020.10.08 |
백준 2406번, 안정적인 네트워크 풀이 (0) | 2020.10.07 |