BOJ_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이 되는 쌍의 개수를 출력한다.
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;
}
Leave a comment