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

요구사항

indexA, indexB, indexC, indexD를 골라서 0이 되게 하는 개수 구하기

 

풀이

4000*4000*4000*4000는 제한시간 초과가 난다

AB 더한 배열 CD 더한 배열을 구하여

AB 오름차순 index : i

CD 내림차순 index : j

으로 0이 되는지 확인하여 되면 되는게 몇개인지 계산

0보다 클 경우 j++

0보다 작을 경우 i++

 

아래 코드는 시간초과

 

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

using namespace std;
const int MAX = 4040;
int n;
int map[4040][6];
int vab[MAX*MAX];
int vcd[MAX*MAX];
bool com1(int a, int b) {
	if (a < b) return true;
	return false;
}
bool com2(int a, int b) {
	if (a > b) return true;
	return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> map[i][j];
		}
	}
	//12, 34 따로 저장해줒 배열 완성 시킨 
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vab[cnt] = { map[i][0] + map[j][1] };
			vcd[cnt] = { map[i][2] + map[j][3] };
			cnt++;
		}
	}
	sort(vab, vab+cnt, com1); // 오름
	sort(vcd, vcd+cnt, com2); // 내림
	long long ans = 0;
	int i = 0, j = 0;
	while (i < cnt && j < cnt) {
		int minnum = vab[i];
		int maxnum = vcd[j];
		//cout << "min" << minnum << " " << maxnum << endl;
		if (minnum + maxnum == 0) {
			//ans++;
			//cout << "A" << endl;
			int ncnt = 1;
			int mcnt = 1;
			for (int k = i+1; k < cnt; k++) {
				if (minnum == vab[k]) ncnt++;
			}
			for (int k = j + 1; k < cnt; k++) {
				if (maxnum == vcd[k]) mcnt++;
			}
			ans += (ncnt*mcnt);
			i += ncnt;
			j += mcnt;
		}
		else if (minnum + maxnum < 0) {
			i++;
		}
		else if (minnum + maxnum > 0) {
			j++;
		}
	}
	printf("%lld\n", ans);
}