BOJ_7453 : 합이 0인 네 정수

less than 1 minute read

문제

정수로 이루어진 크기가 같은 배열 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이 되는 쌍의 개수를 출력한다.

C++ 코드

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n), d(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}

	// 두 배열의 모든 합을 구함
	vector<int> first, second;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			first.push_back(a[i] + b[j]);
			second.push_back(c[i] + d[j]);
		}
	}
	// 한쪽 배열만 정렬하고
	// first 값과 더해서 0 이되는 수를 찾는다.
	// equal_range 함수를 사용하면
	// 시간을 줄일 수 있다!!!
	sort(second.begin(), second.end());
	long long ans = 0;
	for (int num : first) {
		auto p = equal_range(second.begin(), second.end(), -num);
		ans += p.second - p.first;

	}
	cout << ans << '\n';





	return 0;
}

Updated:

Leave a comment