[백준-2473] 세 용액

약간의 기술이 필요한 투 포인터 문제였다.

일단 기본적으로 5000의 입력값에 1초의 제한시간이기 때문에 O(N^2) 의 복잡도까지는 잘 통과할 것이다. O(N*NlogN) 까지도 가능할거라 생각한다.

여튼 3개의 용액을 골라야 하므로 N의 복잡도는 첫 시작 용액을 고르는 것에, 나머지 N은 투포인터 탐색으로 나머지 2개의 용액을 고르는 것에 사용하여 O(N^2)의 복잡도로 끝마무리 할 수 있다.

로직은 다음과 같다.

• 첫 번째 용액을 순서대로 선택한다.
• 고른 용액 이후의 용액들 중 2개의 용액을 투포인터 탐색을 통해 찾는다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;
typedef long long LL;

LL arr[5001];
int main() {
	LL n;
	scanf("%lld", &n);

	for (LL i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + n);
	vector<LL> ans(3);
	LL minn = 21474836470, calc, mid;
	for (LL a = 0; a < n; a++) {
		mid = arr[a];
		for (LL lo = a + 1, hi = n - 1; lo < hi; ) {
			calc = arr[lo] + arr[hi] + arr[a];
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				ans[2] = mid;
			}
			if (calc < 0) {
				lo++;
			}
			else {
				hi--;
			}
		}
	}
	
	sort(ans.begin(), ans.end());
	printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);
	return 0;
}

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

2473번: 세 용액