백준 7453: 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

 

풀이

A[a], B[b], C[c], D[d]의 모든 경우를 다 세어본다면 시간복잡도가 $O(N^4)$이지만, $N\leq 4000$이므로 12초 안에 해결할 수 없습니다.

그러면 Meet in the middle 알고리즘으로 시간복잡도를 줄여보겠습니다.

 

우선 A의 모든 원소와 B의 모든 원소의 합을 담은 배열 AB, C의 모든 원소와 D의 모든 원소의 합을 담은 배열을 CD라 정의합시다. 그러면 AB와 CD를 구하기까지의 시간복잡도는 $O(N^2)$이 됩니다.

 

그러고 나서 CD를 정렬합시다. CD를 정렬하는 시간복잡도는 $O(N^2logN^2)=O(N^2logN)$이 됩니다.

 

AB의 각 원소마다 -AB[i]를 CD에서 찾아줍니다. 이때는 upper_bound와 lower_bound를 활용하여 CD에 -AB[i]가 몇 개 있는지 찾아서 cnt 변수에다 더해줍니다. 이 처리의 시간복잡도는 $O(N^2logN)$이 됨을 알 수 있습니다.

 

따라서 $O(N^4)$이나 되는 시간복잡도를 $O(N^2logN)$까지 줄였기 때문에, 문제 제한 시간 안에 통과가 됩니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int a[4000], b[4000], c[4000], d[4000];
int ab[16000000], cd[16000000];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    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++) {
            ab[j+i*n]=a[i]+b[j];
            cd[j+i*n]=c[i]+d[j];
        }
    }
    long long cnt=0;
    sort(cd, cd+n*n);
    for(int i=0; i<n*n; i++) cnt+=upper_bound(cd, cd+n*n, 0-ab[i])-lower_bound(cd, cd+n*n, 0-ab[i]);
    cout << cnt;
}

 

감사합니다.