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

https://www.acmicpc.net/problem/7453

 

모든 (a, b, c, d) 쌍에 대해서 4중 반복문(시간 복잡도 = O(n^4))을 돌리면 4000^4 = 256,000,000,000,000번의 연산이 필요하고, 1초에 10^8번의 연산이 가능하다고 가정하면 2,560,000초가 걸린다. 즉, 시간 안에 해결 불가능하다. 

 

그런데 모든 (a, b) 쌍에 대한 합을 ab로 구해두고, 모든 (c, d) 쌍에 대한 합을 cd로 구해둔 뒤, ab + cd = 0이 되는 (ab, cd) 순서쌍을 찾으면 2중 반복문으로 문제를 해결할 수 있다. 

ab 구하기: 시간 복잡도 = O(n^2)

cd 구하기: 시간 복잡도 = O(n^2)

ab + cd = 0이 되는 (ab, cd) 순서쌍 찾기: 시간 복잡도 = O(nlogn) (이분탐색 한번 하면 logn인데 그걸 n번 해야하므로 nlogn) (주의할 점은 여기서 n은 4000^2이다)

즉, 네 개의 배열을 먼저 둘씩 묶어 두 개의 배열로 만들고 쌍을 찾으면 시간 복잡도 O((n^2)logn)으로 문제를 해결할 수 있다. 

 

단순히 둘씩 묶어서 푸는 풀이가 이렇게 시간 복잡도를 크게 줄일 수 있다는 것이 신기했다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> arr(n, vector<int>(4));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> arr[i][j];
        }
    }

    vector<int> ab;
    vector<int> cd;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ab.push_back(arr[i][0] + arr[j][1]);
            cd.push_back(-(arr[i][2] + arr[j][3]));
        }
    }

    sort(cd.begin(), cd.end());
    long long ans = 0;

    for (int x: ab) {
        ans += upper_bound(cd.begin(), cd.end(), x) - lower_bound(cd.begin(), cd.end(), x);
    }

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

(AC)