[BOJ] 백준 7453 합이 0인 네 정수

문제 링크

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

풀이

$a+b+c+d = 0$인 조합의 개수를 찾아야합니다. 나이브하게 풀면 $O(N^4)$의 복잡도로 통과하지 못합니다.

 

1) 이를 $a+b = -(c+d)$로 생각하여 양 변을 따로 봅시다.

각각 $(a+b)$, $(c+d)$의 모든 조합을 구하는데 $O(N^2)$의 복잡도가 듭니다.

 

2) $a+b$ 배열의 각 원소마다, $c+d = -(a+b)$를 만족하는 $c+d$ 조합의 수를 찾아줍시다.

upper bound와 lower bound를 이용하면 원하는 구간의 길이를 $O(logN)$에 구할 수 있습니다. 

 

총 시간복잡도 $O(N^2\cdot logN)$으로 충분히 통과가 가능합니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;

vi x, y;
int n, a[4444], b[4444], c[4444], d[4444];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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(all(x));
    sort(all(y));
    ll ans = 0;
    for (int i = 0; i < n * n; i++) {
        ans += upper_bound(all(y), -x[i]) - lower_bound(all(y), -x[i]);
    }
    cout << ans;
}