[BOJ 7453] 합이 0인 네 정수

🔗Link

문제
풀이

💡Idea

4개의 배열을 전부 선형탐색해서 합을 구한다면, O(n⁴)이 걸릴 것이다. n이 4000이므로 64×10¹⁶의 연산이 필요하고, 12초에 동작하기 위해선 다른 방법을 생각해야 한다.
우선 배열을 2개씩만 합해서, AB 배열과 CD 배열을 만든다. n²의 연산이 필요하겠다. 거기서 두 배열을 정렬을 한다면 n²log(n²). 배열 AB에서 각 원소마다 0을 만드는 값을 배열 CD에서 이분탐색을 한다면, n²log(n²). (참고로, 0을 만드는 숫자가 여러 개 있을 수 있음을 주의하자.) 따라서 최종 O(n²log(n²))에 동작하도록 할 수 있고, 12초내에 통과할 수 있겠다.

이분탐색으로 구현하지 않고, AB 배열은 작은 숫자부터, CD 배열은 큰 숫자부터 순회해서 합이 0인 것들을 세어주어도 되겠다. 이런 방식은 meet in the middle이라고 부른다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

int n;
int A[4000], B[4000], C[4000], D[4000];
int AB[16'000'000], CD[16'000'000];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	int n2 = n * 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++) {
			AB[i*n + j] = A[i] + B[j];
			CD[i*n + j] = C[i] + D[j];
		}
	}

	sort(AB, AB + n2);
	sort(CD, CD + n2);

	long long cnt = 0;
	for (int i = 0; i < n2; i++) {
		//cout << AB[i] << " " << CD[i] << '\n';
		int* l = lower_bound(CD, CD + n2, -AB[i]);
		int* u = upper_bound(l, CD + n2, -AB[i]);
		cnt += u-l;
	}

	cout << cnt;

	return 0;
}

🗨️ Side Notes

이분 탐색을 할 CD 배열만 정렬시켜줘도 잘 동작하겠지만, AB 배열을 정렬시켜주면 더 빠르게 동작하더라. 아무래도 이분 탐색을 위해 배열에 접근할 때, 캐시 히트가 더 잘 일어나서 그렇지 않을까 싶다. AB도 정렬 CD만 정렬