BOJ 2473. 세 용액
랭크 : 골드3
문제 풀이
배열을 정리하고, for문으로 첫번쨰 인자를 정하고, 뒤에는 투포인터로 앞뒤로 좁히면서 적절한 값을 찾습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
long long N, ans1, ans2, ans3;
long long ans0 = __LONG_LONG_MAX__;
long long abss(long long num) {
if (num < 0) return -num;
else return num;
}
int main() {
fastio;
cin >> N;
vector<long long> arr(N, 0);
for (int i=0; i < N; i++) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
for (int i=0; i < N-2; i++) {
int start = i + 1;
int end = N - 1;
while (start != end) {
long long sums = arr[i] + arr[start] + arr[end];
if (abss(sums) < ans0) {
ans1 = arr[i]; ans2 = arr[start]; ans3 = arr[end];
ans0 = abss(sums);
}
if (sums >= 0) end--;
else start++;
}
}
cout << ans1 << " " << ans2 << " " << ans3 << endl;
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| two pointer | O(N ^ 2) | O(N) |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 9466. 텀 프로젝트 (0) | 2022.07.10 |
|---|---|
| BOJ 1208. 부분수열의 합 (0) | 2022.07.10 |
| BOJ 1005. ACM Craft (0) | 2022.07.08 |
| BOJ 1806. 부분합 (0) | 2022.07.07 |
| BOJ 9527. 1의 개수 세기 (0) | 2022.07.07 |