[c++] 백준 - 합이 0인 네 정수 ( 이분탐색)

1. 문제

2. 입출력 및 예제

3. 문제 해설

처음에 이 문제를 접했을 때 비슷한 문제가 생각났다. 백준-피자판매 문제와 백준-두배열의 합 문제였다. 따라서 처음엔 두 문제와 같이 map을 사용해서 풀면 쉽게 풀릴 줄 알았다. 위의 두 문제의 경우 가능한 모든 합의 경우의 수를 미리 구해두어 map에 그 합과 그 합이 나오는 경우의 수를 모두 저장해둔다. 그 후 다른 배열을 돌면서 합이 K가 되는 경우를 구해야한다면 cnt += map[K - 다른배열[i]]와 같은 로직으로 경우의 수를 모두 구해 더해주면 되었다. unordered_map의 경우 정렬을 하지 않는 map이고 hash table을 기반으로 하는 자료구조이기 때문에 O(1)의 시간복잡도로 원하는 자료에 접근이 가능했다. 하지만 위의 접근 방법으로 풀었을 경우 메모리 초과가 나왔다. unordered_map 두개를 이용했을 뿐인데 1024MB가 부족하다니... map은 정말 메모리를 많이 쓰는 거 같다. 

 

그래서 그냥 map을 이용하지 말고 배열을 이용하기로 했다. 배열을 이용하려면 이분탐색을 통해 찾아야 시간 복잡도 안에 찾을 수 있을 거 같았고 따라서 정렬을 해준 후 lower_bound와 upper_bound 메소드를 이용해 자신의 -를 붙인 같은 수를 찾기로 했다. 

 

따라서 작성한 코드는 다음과 같다. 

 

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <algorithm>
#include <unordered_map>
#define ll long long
using namespace std;

int N; // 배열의 크기
int NN;
ll A[4001]; //4KB
ll B[4001]; // 4KB
ll C[4001]; // 4KB
ll D[4001]; // 4KB
ll ans;
//unordered_map<ll, int> ab;
//unordered_map<ll, int> cd;
ll AB[16000000 + 4];
ll CD[16000000 + 4];
void input() {
	scanf("%d", &N);
	NN = N * N;
	for (int i = 0; i < N; i++) {
		scanf("%lld %lld %lld %lld", 
			&A[i] , &B[i], &C[i], &D[i]);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			/*ab[A[i] + B[j]]++;
			cd[C[i] + D[j]]++;*/
			AB[i * N + j] = A[i] + B[j];
			CD[i * N + j] = C[i] + D[j];
		}
	} // 4000 * 4000
}

void sol() {
	sort(AB, AB + NN);
	sort(CD, CD + NN);

	for (int i = 0; i < NN; i++) {
		ll cnt = upper_bound(CD, CD + NN, -AB[i]) - lower_bound(CD, CD + NN, - AB[i]);
		ans += cnt;
	}
	/*for (auto a : ab) {
		ans = ans + ab[a.first] * cd[-a.first];
	}*/
	printf("%lld\n", ans);
}
int main() {
	input();
	sol();
	return 0;
}

주석 처리된 코드는 map을 이용해 풀던 방식이다. 

 

도전의 흔적들...