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이 되는 쌍의 개수를 출력한다.

예제 입력 1 복사

6

-45 22 42 -16

-41 -27 56 30

-36 53 -37 77

-36 30 -75 -46

26 -38 -10 62

-32 -54 -6 45

A    B   C  D

예제 출력 1 복사

5

 

---

풀이 :  A+B+C+D = 0;

A+B = -(C+D)

1. A+B 해서 나오는 모든 값 배열에 저장

2. C+D 해서 나오는 값에서 마이너스 한값 이랑 A+B에 있는 값이 있는지 없는지 검사  --> equal_range 사용하기!

---

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n);
	vector<int> d(n);
	
	// 각 배열 받기
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}

	//A+B
	vector<int> x;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			x.push_back(a[i] + b[j]);
		}
	}
	
	// 정렬 해주기
	sort(x.begin(), x.end()); 
	
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			pair<std::vector<int>::iterator, std::vector<int>::iterator> p = equal_range(x.begin(), x.end(), -(c[i] + d[j]));
			ans += (p.second - p.first);
		}
	}
	cout << ans << '\n';
	return 0;
}