[백준] C++ 세 용액(2473)

이 문제는 용액과 비슷한 문제이다.

세 종류의 용액을 합쳐서 그 합이 0에 가장 가깝게 만드는게 목표이다.

 

용액 문제는 두 개의 용액을 합쳐서 그 합이 0에 가장 가깝게 만드는 문제였다.

 

이렇게 시작점과 끝점에 S와 E를 두고 합쳤을 때 합이 만약 0보다 크면 e를 --해주고 합이 0보다 작으면 s를 ++해줘서 문제를 해결해 주었다.

 

세 용액은 두 가지의 용액이 아니라 세 가지의 용액을 가지고 합이 0에 가깝게 만드는 목표이다. 그러면 어떻게 하면 세 가지 용액을 구할 수 있을까?? 위 용액문제에서 조금만 수정하면 된다.

-97을 무조건 하나의 용액에 포함한다고 가정하자. 그러면 나머지 두 용액의 합이 97이 되어야 합이 0이 될 것이다. 나머지 두 용액의 합이 97에 가장 가까운 조합을 찾으면 된다.

 

-97에 대한 계산이 완료되었으면 이번에는 -6을 무조건 포함시킨다.

나머지 두 용액의 합이 6에 가까운 조합을 찾는다.(왜 -97은 이제 계산에 포함을 안 시키는가?? 이미 이전에 -97을 포함한 조합을 모두 살펴보았기 때문에 볼 필요가 없음.)

이런 식으로 문제를 해결하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

long long arr[5001];

int main(void)
{
	int N = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + N);



	int result1 = 0;
	int result2 = 0;
	int result3 = 0;

	long long min = 3000000001;
	for (int i = 0; i < N - 2; i++)
	{
		int start = i + 1;
		int end = N - 1;
		while (start < end)
		{
			long long sum = arr[start] + arr[end] + arr[i];
			if (min > abs(sum))
			{
				min = abs(sum);
				result1 = arr[i];
				result2 = arr[start];
				result3 = arr[end];
			}

			if (arr[start] + arr[end] > -arr[i])
			{
				end--;
			}
			else
			{
				start++;
			}

		}
	}



	cout << result1 << " " << result2 << " " << result3;

	return 0;
} //-97 -6 -2 6 98