BOJ 2473 - 세 용액

2473번: 세 용액 (acmicpc.net)

2473번: 세 용액

 

접근 방법

용액 문제와 비슷하게 해결 가능한 투 포인터 문제이다.

세 용액의 합이 0에 가장 가까운 용액들을 고르는 문제이기 때문에 

처음엔 두 개의 용액을 모두 더 한 배열을 이용하여, 나머지 용액을 투포인터로 선정하는 방법을 사용했다.

 

 

struct st{

  int a; // 용액A

  int b; // 용액B

  int sum; // 용액A + 용액B

}

위 구조체를 이용하여 vector<st> sumArray 와 vector<long long> arr 이렇게 두 개의 백터를 이용하였다.

결과는 나왔지만 메모리 초과가 나와서 다른 방법을 구상해보았다.

 

그래서 이분탐색을 이용하기로 했다.

두개의 용액(용액A,B)을 선정하고, 나머지 하나(용액C)를 이분탐색으로 선정하기로 했다.

그런데 문제가 용액A, 용액B와 용액C가 중복되는 사태가 발생했다.

중복처리를 하기에 코드 상 까다롭게 되어 다른 방법을 모색했다.

 

용액의 수가 5000까지이므로 하나의 용액을 선정하고, 나머지 용액을 투포인터로 선정하는 방식을 사용하기로 했다.

메모리도 초과되지 않고, O(N*(N/2))로 해결할 수 있다.

 

코드

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

#define MAX 5001
#define ll long long

vector<ll> arr;
vector<ll> res;
ll tmp = 9999999999999999;
ll n, s;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

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

	for (int i = 0; i < n; i++) {
		int l = 0;
		int r = n - 1;

		bool flag = false;

		while (l < r)  {
			ll sum = arr[l] + arr[r] + arr[i];
			
			if (r == i) {
				r--;
				continue;
			}
			if (l == i) {
				l++;
				continue;
			}
				
			if (sum == 0) {
				res.clear();
				res.push_back(arr[l]);
				res.push_back(arr[r]);
				res.push_back(arr[i]);
				flag = true;
				break;
			}

			if (abs(sum) < tmp) {
				tmp = abs(sum);
				res.clear();
				res.push_back(arr[l]);
				res.push_back(arr[r]);
				res.push_back(arr[i]);
			}
			
			if (sum < 0) {
				l++;
			}
			else if (sum > 0) {
				r--;
			}

		}
		if (flag)
			break;
	}
	
	sort(res.begin(), res.end());

	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << ' ';
	}
}