백준 2473 C++

백준 2473

주어진 배열 중 세 용액을 골라서, 합을 최대한 0으로 만드는 용액들을 출력하는 문제이다.

N이 5000이니 O(N^2)로 2중 for문으로 2개를 고른 후, 나머지 1개는 lower_bound로 고른다.

lower_bound는 해당 값, 혹은 해당 값보다 큰 숫자가 첫 번째로 어디서 등장하는지가 중요하므로, 나올 수 있는 후보는 idx, idx - 1이다. 그리고, 기존 인덱스와 중복 방지 if문을 넣어준 후에 그걸 골라주면 된다.

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


using namespace std;
vector<long long> v1;
int N;

vector<long long> ans;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	v1.resize(N);
	for (int y = 0; y < N; ++y) {
		cin >> v1[y];
	}
	sort(v1.begin(), v1.end());

	int s = 0, e = N - 1;

	long long maxi = 1e18;
	for (int y = 0; y < N; ++y) {
		for (int x = y + 1; x < N; ++x) {
			long long sum = v1[y] + v1[x];

			//lower_bound -> -sum보다 같거나 큰 숫자가 어디에서 등장하는지. 
			int idx = lower_bound(v1.begin(), v1.end(), -sum) - v1.begin();

			if (idx > 0) {
				if (y != idx - 1 && x != idx - 1 && maxi > abs(sum + v1[idx - 1])) {
					maxi = abs(sum + v1[idx - 1]);
					ans.clear();
					ans.push_back(v1[y]);
					ans.push_back(v1[x]);
					ans.push_back(v1[idx - 1]);
				}
			}

			if (idx < N) {
				if (y != idx && x != idx  && maxi > abs(sum + v1[idx])) {
					maxi = abs(sum + v1[idx]);
					ans.clear();
					ans.push_back(v1[y]);
					ans.push_back(v1[x]);
					ans.push_back(v1[idx]);
				}
			}

		}
	}

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

	for (auto aa : ans) {
		cout << aa << " ";
	}
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기