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

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

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

 

 문제

 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

 A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

 입력

 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

 

 

 출력

 합이 0이 되는 쌍의 개수를 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n; cin >> n;
	long long a[4000], b[4000], c[4000], d[4000];
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	
	vector<long long> v1;
	vector<long long> v2;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			v1.push_back(a[i]+b[j]);
			v2.push_back(c[i]+d[j]);
		}
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	
	
	long long cnt=0;
	for(int i=0;i<n*n;i++){
		long long s = -v1[i];

		int t1 = lower_bound(v2.begin(), v2.end(), s) - v2.begin();
		int t2 = upper_bound(v2.begin(), v2.end(), s) - v2.begin();
		if(v2[t1] == s){
			cnt += t2 - t1;
		}
	}
	cout << cnt;
	return 0;
}

 앞의 9847번 문제와 유사한 문제라고 생각했다가 시간초과를 받았다. n이 4000까지라 배열 두개를 합쳐서 처리하는 방법으로 했어야 했고, 0이 되는 네 정수쌍 1개 찾으면 끝이 아니라 몇개가 있는지를 알아내야 하는 문제로 lower_bound, upper_bound를 필수로 알고 있어야하는 문제였다.

이중포문에 나머지 두개 배열 더한것에 이분탐색을 진행하는 방법이 시간초과가 났었는데, 이중포문 대신 똑같이 두개 배열 더한 새로운 벡터를 만들어 정렬한 뒤 찾도록 하니 시간초과가 해결되었다. 찾아보니 "AB를 정렬할 경우 CD를 이분탐색할 때 연속적으로 이전에 봤던 위치들을 중심으로 다시 탐색하게 될 확률이 높아집니다. CD의 크기가 매우 크다는 것을 감안할 때 대부분의 위치를 매번 메모리로부터 불러오지 않고 캐시에서 찾아낼 수 있으므로 훨씬 시간이 절약됩니다. AB를 정렬하지 않으면 CD에서 찾는 위치가 매번 달라질 확률이 높아지므로 캐시 안에 들어가지 않는 수많은 페이지들을 지속적으로 갈아끼워야 할 확률이 높아져 시간이 오래 걸리게 됩니다." 라고 한다. (https://www.acmicpc.net/board/view/74585 (djm03178님)) 코테에서 이런 이유로 시간초과 문제에 직면한 것이 처음이라 이런 것까지 고려해야하나 싶은 생각이 들긴했지만 알아두면 좋을 것 같다.