[BOJ/C++] 7453(합이 0인 네 정수)

1. Link

https://www.acmicpc.net/problem/7453

2. 풀이 과정

1. 4개의 배열의 각 인덱스별 합을 구해야함 -> 배열의 최댓값 4000의 4제곱이면 TLE
2. 40004000log(4000*4000)으로 시간 충족 가능 -> 이분 탐색

• 4개의 배열을 2개씩 합을 구하는 것으로 4000*4000(1600만)으로 시간 단축을 꾀함
• 1600만에서 다른 배열에서 조건에 부합하는 값을 찾기 위해 log(40004000)으로 대략 1600만24 정도의 시간을 사용하도록 구현 -> 시간 제한 12초이므로 문제는 없을 것으로 확인

3. 정답 코드

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

int n;
int a[4001][4];
vector<int> x, y;

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			cin >> a[i][j];
		}
	}
}

void solution() {
	input();
	long long answer = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			x.push_back(a[i][0] + a[j][1]);
			y.push_back(a[i][2] + a[j][3]);
		}
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	for (int i = 0; i < n * n; ++i) {
		answer += upper_bound(y.begin(), y.end(), -x[i]) 
			    - lower_bound(y.begin(), y.end(), -x[i]);
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}