[백준 C++] 2473번: 세 용액

1. 문제

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

2473번: 세 용액

 

2. 알고리즘 분류

• 정렬
• 이분 탐색
• 두 포인터

 

3. 소스 코드

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

 

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

using namespace std;

long long solutions[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;

	// 전체 용액의 수(N) 입력
	cin >> N;

	// 용액의 특성값 입력
	for (int i = 0; i < N; i++)
		cin >> solutions[i];

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

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

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

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

	return 0;
}

 

4. 유용한 문법 및 알고리즘

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

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