[PS] 합이 0인 네 정수 / C++ (백준 7453번)

 

구현은 매우 쉽지만 발상하는데 시간이 꽤 걸렸던 문제

A B의 합, C D의 합을 모두 구한 배열(각각 최대 1600만) 2개를 만든 뒤 정렬하여 two pointer, binary search를 사용하여 합이 0인 쌍의 개수를 구하면 된다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll> vec1, vec2;
ll a[4001], b[4001], c[4001], d[4001];

int binary_search(int en, int target) {
	int st = 0;
	while (st < en) {
		int mid = (st + en) / 2;
		if (vec2[mid] == target) {
			en = mid;
		}
		else {
			st = mid + 1;
		}
	}
	return en;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld %lld %lld", &a[i], &b[i], &c[i], &d[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			vec1.push_back(a[i] + b[j]);
			vec2.push_back(c[i] + d[j]);
		}
	}
	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());
	long long dap = 0;
	int n1 = 0, n2 = vec2.size() - 1, vec1_size = vec1.size();
	while (1) {
		if (n1 == vec1_size || n2 == -1)break;
		if (vec1[n1] + vec2[n2] == 0) {
			int f_same = binary_search(n2, vec2[n2]);
			n1++;
			dap += n2 - f_same + 1;
		}
		else if (vec1[n1] + vec2[n2] > 0)
			n2--;
		else
			n1++;

	}
	printf("%lld\n", dap);
	return 0;
}