BOJ 7453 : 합이 0인 네 정수

• 문제 링크 : boj.kr/7453
• 난이도 : G2
• 태그 : 정렬, 이분탐색, 중간에서 만나기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<array<int, 4>> arr(n);
    for(auto &u : arr) {
        cin >> u[0] >> u[1] >> u[2] >> u[3];
    }
    vector<int> A;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            A.emplace_back(arr[i][0] + arr[j][1]);
        }
    }
    sort(all(A));
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            ll sum = arr[i][2] + arr[j][3];
            ans += upper_bound(all(A), -sum) - lower_bound(all(A), -sum);
        }
    }
    cout << ans;

    return 0;
}

---

풀이

단순하게 구하면 O(N^4)로 값이 매우 커진다. 이를 (A,B), (C,D) 두 부분으로 나누어 구하면 각각 O(N^2)로 구할 수 있다.

이제 한 부분과 다른 한 부분의 합이 0이 되는 쌍을 찾으면 된다.

(A,B)쌍의 합을 정렬하고, (C,D)쌍의 원소가 합이 0이 되도록 하는 값을 이분탐색으로 찾을 수 있다.

최종적으로 시간복잡도는 O(N^2log(N^2))이다.