문제 간략 설명

N개의 용액 특성값이 주어진다. 세 용액을 혼합했을 때의 특성값은 세 용액의 특성값의 합이다. 0에 가장 가까운 특성값을 만드는 세 용액을 찾아서 그 특성값들을 오름차순으로 출력한다.

풀이 방법

  1. 배열을 정렬한다.
  2. 정렬된 배열에서 하나의 용액을 고정하고, 나머지 두 개를 투포인터로 탐색한다.
  3. 용액 하나씩에 대해서 투포인터로 남은 배열을 검사하므로 시간복잡도 O(N^2)

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long ll;

int N;
int res[3];

vector<int> vec;

ll sum;
ll _min = LLONG_MAX;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	vec.resize(N);

	for (int i = 0; i < N; i++)
		cin >> vec[i];

	sort(vec.begin(), vec.end());

	for (int i = 0; i < N - 2; i++) {
		int left = i + 1, right = N - 1;

		while (left < right) {
			sum = (ll)vec[i] + vec[left] + vec[right];
			ll sum_abs = abs(sum);

			if (sum_abs < _min) {
				res[0] = i;
				res[1] = left;
				res[2] = right;
				_min = sum_abs;
			}

			if (sum > 0)
				right--;
			else
				left++;
		}
	}

	cout << vec[res[0]] << " " << vec[res[1]] << " " << vec[res[2]] << endl;

	return 0;
}

Key Points