[백준] 7453번: 합이 0인 네 정수

📌 문제

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

📌 설명

이분 탐색을 통해 해결하였다. 주어진 네 배열을 두 배열 간 합을 통해 두 개의 배열로 축소시킨다. 정렬 후 이분탐색을 진행하면 된다.

주의해야 할 점은 가능한 답의 가짓수가 4000^4이라는 점이다. 따라서 long long 자료형을 사용해야 한다. 또한 중복된 원소가 존재하는 것에 조심해야 한다. 축소된 두 배열의 합이 0일 때 1을 증가시키면 안 된다. 합이 0이 되는 첫 번째 원소를 찾기 위해 lower_bound를 사용하였고 합이 0인 다른 원소들의 개수를 구하기 위해 upper_bound를 사용하였다.

📌 코드

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

using namespace std;

vector<int> v[4]; // A, B, C, D
vector<int> sum[2]; // A+B, C+D

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			int x;
			cin >> x;
			v[j].push_back(x);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum[0].push_back(v[0][i] + v[1][j]);
			sum[1].push_back(v[2][i] + v[3][j]);
		}
	}

	sort(sum[0].begin(), sum[0].end());
	sort(sum[1].begin(), sum[1].end());

	long long cnt = 0;
	for (int i = 0; i < sum[0].size(); i++) {
		int tar = lower_bound(sum[1].begin(), sum[1].end(), -sum[0][i]) - sum[1].begin();
		int len = upper_bound(sum[1].begin(), sum[1].end(), -sum[0][i]) - sum[1].begin();
		if (tar < sum[1].size() && sum[0][i] + sum[1][tar] == 0)
			cnt += len - tar;
	}

	cout << cnt;
}