문제 : https://www.acmicpc.net/problem/2473
[ 알고리즘풀이 ]
Input이 5,000이라 O(N^2) 알고리즘을 사용해도 문제를 해결할 수 있습니다. Input을 Sorting 한 후, 모든 용액에 대해 Two Pointer로 Binary Search를 진행하면 O(N^2)으로 모든 경우의 수를 다룰 수 있습니다.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define INF 999999999999999
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, t;
vector<long long> list;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> t;
list .push_back(t);
}
sort(list.begin(), list.end());
long long ans1, ans2, ans3;
long long ansSum = INF;
for (int i = 0; i < N; i++) {
int left = i + 1, right = N - 1;
while (left < right) {
long long sum = 1LL*(list[i] + list[left] + list[right]);
if (abs(sum) < ansSum) {
ansSum = abs(sum);
ans1 = list[i], ans2 = list[left], ans3 = list[right];
}
if (sum < 0)
left++;
else if(sum > 0)
right--;
else {
i = N;
break;
}
}
}
cout << ans1 << ' ' << ans2 << ' ' << ans3;
return 0;
}
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 14500 : 테트로미노 - travelbeeee (0) | 2020.01.23 |
---|---|
[BOJ] 14499 : 주사위 굴리기 - travelbee (0) | 2020.01.23 |
[BOJ] 2467 : 용액 - travelbeeee (0) | 2020.01.22 |
[BOJ] 2470 : 두 용액 - travelbeeee (0) | 2020.01.22 |
[BOJ] 6986 : 절사평균 - travelbeeee (0) | 2020.01.22 |