[기타] 주어진 수열에서 선택한 3개의 값의 합이 0에 가장 가깝게 선택하는 방법

1. 유사 문제

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

2473번: 세 용액

 

2. 소스 코드

Key Point)
1. 투 포인터 알고리즘을 활용하기 위해 정렬한다.
2. 3개의 값을 비교할 때는 하나를 정해 놓고 2개의 값을 '투 포인터' 알고리즘을 통해 계산한다.

 

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

using namespace std;

long long arr[5000];
long long ans[3];

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

	int N;
	long long result = 3000000001;

	// 수열의 크기 입력
	cin >> N;

	// 수열 입력
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	// 오름차순 정렬
	sort(arr, arr + N);

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

		// 투포인터 알고리즘
		while (left < right)
		{
			long long val = arr[i] + arr[left] + arr[right];
			if (abs(val) < result)
			{
				result = abs(val);
				ans[0] = arr[i];
				ans[1] = arr[left];
				ans[2] = arr[right];
			}
			if (val < 0) left++;
			else right--;
		}
	}

	// 결과값 출력
	for (int i = 0; i < 3; i++)
		cout << ans[i] << " ";

	return 0;
}