[ BOJ 7453 ] 합이 0인 네 정수

링크

http://icpc.me/7453

문제

네 개의 배열 A, B, C, D가 주어질 때, A[a]+B[b]+C[c]+D[d]=0이 되는 (a, b, c, d)의 순서쌍의 갯수

즉, 걍 아무거나 네 개 뽑아서 더했을 때 0되게 하는 갯수

풀이

먼저, $N\leq4000$임을 생각해야한다.

이를 왜 생각해야하느냐?

만약 완전탐색 기법으로 A, B, C, D 모든 배열 훑으면서 쓰으으윽 하면 $O(N^4)$이된다.

$4000=4\times10^3$이고, $4000^4=2^8\times10^{12}$인데 이를 1초내에 돌리는건 그냥 불가능하다...

따라서 좀 더 효율적은 방법을 생각해보아야 한다!

Key-Idea : Meet in the Middle

영어로 까리하게 Meet in the middle인데 한국어로 직역하면 중앙에서 만나기이다.

뭔가 갑자기 안좋아진 느낌이긴 한데... 아무튼 중간에서 만나기 기법이란

분할정복 비슷한 느낌이라 보면 된다.

위 사진과 같이 A를 처리하는 문제가 있다 하자. 

하지만, 실제로 A를 처리하면 우리가 원하는 복잡도를 훨씬 넘어버리거나 복잡도는 얼추 맞추어지더라도 시간제한을 초과하는 경우가 많다. 

이런 경우, 우리는 처리해야하는 것을 "2가지"로 쪼갠 후, 각각을 처리해서 합친다. 이가 분할정복이다. 

Meet in the Middle도 비슷하다. 2가지로 쪼갠 후에 합칠 때 앞의 정보를 가지고 합친다만 좀 다를 뿐이다.

이가 Meet in the Middle 기법을 표현한 그림이다. 

그림과 같이 반인 A를 처리하고 나서, B도 처리한다. 

이 때, A의 데이터를 기반으로 B를 처리해주는 방식으로 이루어진다. 

예를 들어 A에서 {3, 4, 5}라는 데이터가 있고, 이를 기반으로 B에서 처리할 때에는 더해서 -3, -4, -5만 되는 값들을 가져오면 된다. 

이 때, 반을 쪼개서 수행하기 때문에 이의 시간복잡도는 $O(N^4)$에서 $O(2N^2)=O(N^2)$으로 줄어들게된다.

풀이(Cont'd)

이를 이용하여 문제를 해결해보자.

앞서 말했듯이, A,B와 C,D에 대한 배열로 쪼개어서 두 개를 따로 처리하는 식으로 문제를 풀어나갈 것이다.

이 때, A,B에 대해서 값을 구했을 때 바로 C,D로 넘겨주면 이는 $O(N^4)$이다.

왜냐? A,B에 대해서 값 찾은 족족 C,D에서도 완전 탐색을 통해서 찾으면 하나의 원소당 $N^2$의 순회가 있게 되고,

A,B의 총 값의 개수는 $N^2$이기 때문에 $N^2\times N^2=N^4$이 되기 때문이다.

Meet in the Middle은 분할정복처럼 각각 데이터를 쪼갠 후에 필요한 값만을 가져와 합치는 것이다.

즉, C,D의 모든 원소의 값의 합을 배열에 담아놓고 A,B의 값마다 배열의 값을 참조하면 된다.

map을 사용해도 되고, 배열에 다 집어넣고 정렬 후에 upper_bound-loewr_bound 하면 구할 수 있다.

코드는 다음과 같다.

코드

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[4005],b[4005],c[4005],d[4005];
    int n;
    long long cnt=0;
    vector<int> x;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d %d %d %d",&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(c[i]+d[j]);
    sort(x.begin(),x.end());
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) 
    {
        auto d=equal_range(x.begin(),x.end(),-a[i]-b[j]);
        cnt+=distance(d.first,d.second);
    }
    return !printf("%lld",cnt);
}