BOJ : 7453 합이 0인 네 정수

---

[BOJ 7453(G2)리뷰]

이전에 풀었던 BOJ : 2143 두 배열의 합 문제와 비슷한 유형의 문제다.

다만 배열의 개수가 2개에서 4개가 되었고, 이번엔 4개의 배열의 합이 0인 쌍들의 개수를 구해야 한다.

과정은 지난 문제와 비슷하다. 다만 조금 로직을 다르게 했다.

일단 먼저 A,B,C,D배열을 AB배열의 두 배열의 합으로 합치고, CD배열의 두 배열의 합으로 합쳤다.
그리고 마찬가지로 오름차순으로 정렬을 해줬다. 

이제 이 두 배열에는 A,B배열을 서로 더한값과 B,C배열을 서로 더한값이 오름차순으로 정렬되어 있다.

처음엔 이 상태에서 투 포인터를 이용해 풀었지만 시간초과를 맞았다. map에 갯수를 세는 과정에서 발생한것이라 생각된다.

그래서 이번엔 합이 0인 쌍들을 구한다는 특성을 이용하여 풀었다. (힌트 참고함..)

즉 A,B배열을 합친 AB배열을 처음부터 끝까지 돈다. 두 배열의 합이 0이기 위해서는 두 배열이 서로 값은 같고 부호만 다른관계여야 한다. 다른 상황에선 합이 0이 될 수가 없다.

따라서 AB배열의 값을 순차적으로 돌며 BC배열에 값은 같고 부호만 다른 관계의 값이 존재하는지 확인하는 작업을 거치면 된다. 그러나 이때 전체를 탐색해서는 안되고 이분탐색을 통해 찾아야 시간 안에 답을 구할 수 있다.

이분탐색을 이용하여 upper_bound와 lower_bound를 이용했다. 만약 해당 값이 배열에 존재한다면 upper의 결과 - lower결과가 조건을 만족하는 데이터의 갯수가 된다. 그리고 이때 조건에 만족하는 값이 없을수도 있으니 반드시 확인을 하고 카운팅 해줘야한다.

/*
	21.01.12
	BOJ : 7453 합이 0인 네 정수 (https://www.acmicpc.net/problem/7453)
	이분탐색
*/
#include <bits/stdc++.h>
using namespace std;

int A[4001];
int B[4001];
int C[4001];
int D[4001];

vector <int> mergeA, mergeB;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}

	//두 개의 배열을 하나의 배열로 만들자.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sum = A[i] + B[j];
			mergeA.push_back(sum);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sum = C[i] + D[j];
			mergeB.push_back(sum);
		}
	}

	//정렬
	//sort(mergeA.begin(), mergeA.end()); //A는 정렬 안해도 상관없음. (다 탐색하므로)
	sort(mergeB.begin(), mergeB.end());

	int i = 0, j = mergeB.size() - 1;

	int len = N * N;
	int sum = 0;
	long long int cnt = 0;
	long long int ans = 0;
	while (i < len) {
		int num = mergeA[i++];

		long long int lo = lower_bound(mergeB.begin(), mergeB.end(), -num) - mergeB.begin();
		long long int hi = upper_bound(mergeB.begin(), mergeB.end(), -num) - mergeB.begin();

		if (-num == mergeB[lo])
			ans += (hi - lo);
	}

	cout << ans;


	return 0;
}