[백준 C++] 7453번 합이 0인 네 정수

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에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$이다.
• 출력: 합이 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 출력 5

## 풀이
중간에서 만나기를 써서 풀면 된다. 그냥 브루트포스를 쓰면 $O(n^4)$만큼의 시간 복잡도를 가지기에 시간 초과가 난다. 따라서 a와 b를 더한 배열과 c와 d를 더한 배열을 비교해서 둘이 빼서 0이 나오면 합이 0인 쌍이 된다. c와 d를 더한 배열의 값들에 -1을 곱해 두면 a와 b를 더한 배열과 같은 경우 합이 0인 쌍이므로 이 상태에서 이진탐색을 하면 된다.
## 어려웠던 점
이진탐색을 할때 그냥 탐색을 해서 있으면 1을 더했는데 cd배열에서 같은 값이 여러개 있는 경우를 생각 못했다. 여러개 있는 경우에는 1이 아닌 여러 값을 더했어야 했다. 따라서 upper_bound와 lower_bound의 차이를 구해서 하면 개수까지 더할 수 있다.

## 배운 점 / 느낀 점
이진탐색을 맨날 구현했는데 STL함수 쓰니까 좋다. upper_bound와 lower_bound의 활용 방법을 알았다. 숫자가 커보여서 무지성으로 longlong했는데 int해보니까 틀린다. 

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long n, r;
vector<long long> a;
vector<long long> b;
vector<long long> c;
vector<long long> d;
vector<long long> ab;
vector<long long> cd;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    a = vector<long long>(n);
    b = vector<long long>(n);
    c = vector<long long>(n);
    d = vector<long long>(n);
    ab = vector<long long>();
    cd = vector<long long>();

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ab.push_back(a[i]+b[j]);
            cd.push_back(-c[i]-d[j]);
        }
    }
    sort(cd.begin(), cd.end());
    r = 0;
    for (int i = 0; i < ab.size(); i++) {
        r += upper_bound(cd.begin(), cd.end(), ab[i]) - lower_bound(cd.begin(), cd.end(), ab[i]);
    }

    cout << r;
    return 0;
}