[BOJ] 2473 세 용액 C++

개요

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

2473번: 세 용액

골드3 난이도 문제다.

풀이

2467번 용액

위 문제와 유사하지만 한 번 더 생각해야 하는 문제다.

3개의 용액을 합성해서 0에 가까운 경우를 구해야 한다.

투 포인터는 O(N)의 시간복잡도를 가진다.

따라서 앞에서부터 모든 원소를 기준으로 한 번씩 잡고, 해당 윈소 이후를 기준으로 양 끝에 투 포인터를 일일이 돌려준다면 O(N^2)가 나올 것이다.

N<=5000 이므로 위 방법으로 1초 이내 연산이 가능하다. (여유롭게 1억번 연산에 1초로 잡자)

코드

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
constexpr int LIMIT = 5002;

int N;
long long water[LIMIT];
int ansFront, ansMid, ansBack;

void TwoPointer()
{
	int front = 0;
	int back = N - 1;
	int mid = 1;
	long long sum = 0;
	long long ansSum = 10000000000;

	while (front < back && ansSum)
	{
		mid = front + 1;
		back = N - 1;

		while (mid < back)
		{
			sum = water[front] + water[mid] + water[back];
			if (abs(ansSum) > abs(sum))
			{
				ansSum = sum;
				ansFront = water[front];
				ansMid = water[mid];
				ansBack = water[back];
			}

			if (sum < 0)mid++;
			else		back--;
		}
		front++;
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

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

	sort(water, water + N);

	TwoPointer();

	cout << ansFront << " " << ansMid << " " << ansBack;
}