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

이 문제는 brute-force로 풀면 O(N^4)로 시간 초과가 난다.

배열 A, B, C, D에서 1개씩 선택해 푸는 것으로는 시간 내에 풀 수 없다는 소리이다.

그럼 여러 수를 더해두고 0을 만들기 위해 필요한 값이 있는지 확인하는 방식으로 접근해서 시간 복잡도를 떨어뜨려야 한다.

마음 같아서는 숫자 3개를 더해놓고 배열 a에서 1개씩 가져와 -a[i]가 존재하는지 확인하고 싶지만, 공간복잡도가 O(N^3)이 되어 메모리 초과가 나게된다.

따라서, 최대 2개의 원소까지만 더한 결과를 저장해 둘 수 있다.

그런데, 문제의 목표는 A[a] + B[b] + C[c] + D[d] = 0을 만족하는 쌍을 찾는 것이다.

그렇다면, 배열 A와 B, C와 D의 가능한 쌍의 합을 저장할 필요 없이, C와 D의 원소 쌍들의 합을 저장해 두고, A와 B에서는 2중 루프를 돌면서 원소를 꺼내 -a[i] - b[j]가 몇 개 있는지 확인하면, 쉽게 답을 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n;
int a[4000], b[4000], c[4000], d[4000];
int two[16'000'002];

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

    cin >> n;
    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++)
            two[n * i + j] = c[i] + d[j];
    }

    int sz = n * n;
    sort(two, two + sz);

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cnt += upper_bound(two, two + sz, -a[i] - b[j]) -
                   lower_bound(two, two + sz, -a[i] - b[j]);
        }
    }
    cout << cnt;
}

하지만, 여기서 캐시 히트가 일어날 수 있도록 한다면, 처리 속도는 더 빨라질 것이다.

이렇게 하기 위해서는 중복되는 값을 곧바로 처리하도록 하면 된다.
그러기 위해서, 배열 A와 B의 원소 쌍들의 합도 배열에 저장해 정렬해두어야 한다.
그래야 중복된 값이 곧바로 처리가 된다는 것이 보장되고 이는 캐시 히트율 상승으로 연결된다.

#include <bits/stdc++.h>
using namespace std;

int n;
int a[4000], b[4000], c[4000], d[4000];
vector<int> x, y;

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

    cin >> n;
    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++) {
            x.push_back(a[i] + b[j]);
            y.push_back(c[i] + d[j]);
        }
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    long long cnt = 0;
    for (auto e : x)
        cnt += upper_bound(y.begin(), y.end(), -e) -
               lower_bound(y.begin(), y.end(), -e);
    cout << cnt;
}

여기서 더 나아가 좌표 압축을 통해 연산 횟수를 줄여줄 수 있다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
using ll = long long;

int n;
int a[4000], b[4000], c[4000], d[4000];
vector<int> x, y;
vector<pair<ll, ll>> cx, cy; // compressed x, y

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

    cin >> n;
    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++) {
            x.push_back(a[i] + b[j]);
            y.push_back(c[i] + d[j]);
        }
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    cx.push_back({x[0], 1});
    for (int i = 1; i < x.size(); i++) {
        if (cx.back().X == x[i])
            cx.back().Y++;
        else
            cx.push_back({x[i], 1});
    }
    cy.push_back({y[0], 1});
    for (int i = 1; i < y.size(); i++) {
        if (cy.back().X == y[i])
            cy.back().Y++;
        else
            cy.push_back({y[i], 1});
    }

    ll cnt = 0;
    for (auto e : cx) {
        auto l = lower_bound(cy.begin(), cy.end(), make_pair(-e.X, 1ll));
        if (l->X == -e.X)
            cnt += e.Y * l->Y;
    }
    cout << cnt;
}

하지만, 캐싱을 이용하는 것이 압축한 것보다 더 빠른 것을 확인할 수 있다. 아마도 테스트 케이스들에서는 유의미한 영향을 줄정도로 중복이 많지 않았던 것 같다.