백준 문제 7453번 합이 0인 네 정수 문제풀이 c++

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

7453번: 합이 0인 네 정수

 

문제해석

전에 풀어봤던 3151번 합이 0 문제와 비슷한 문제 같다는 느낌을 받았다. https://www.acmicpc.net/problem/3151

다만 3151번은 3개 합이 0이 되는 쌍의 갯수를 찾는 것 이고 이 문제는 4개 합이 0이 되는 쌍의 갯수를 찾는 것 이다.

 

그냥 모든 경우를 확인해버리면 배열의 크기가 최대 4000개 이므로 4000^4 이므로 이렇게 풀면 시간초과가 난다.

 

그렇다면 두 쌍씩 묶어서 생각해보자 

첫번째 그룹을 A배열과 B배열의 쌍 최대 4000^2=16000000가지

두번째 그룹을 C배열과 D배열의 쌍 최대 4000^2=16000000가지

 

그리고 두번째 그룹을 정렬 후 첫번째 그룹의 원소의 -1을 곱한것들을 차례로 두번째 그룹에서 이분탐색을 해본다.

만약 존재한다면 그 A B C D는 합이 0이 되는 4개의 쌍이 된다.

 

이렇게 하면 O(n^2+n^2+n^2logn^2)=O(n^2logn^2)의 시간복잡도를 가지므로 문제를 시간 안에 해결 할 수있다.

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
typedef long long int ll;
using namespace std;
vector <ll> v;
vector <ll> u;
ll A[4000];
ll B[4000];
ll C[4000];
ll D[4000];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n; cin>>n;
    ll sum=0;
    for(ll 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++)
        {
            v.push_back(A[i]+B[j]);
            u.push_back(C[i]+D[j]);
        }
    }
    sort(u.begin(),u.end());
    for(int i=0; i<v.size(); i++)
    {
        ll x=upper_bound(u.begin(),u.end(),-v[i])-u.begin();
        ll y=lower_bound(u.begin(),u.end(),-v[i])-u.begin();
        if(u[y]==-v[i])
        {
            sum=sum+x-y;
        }
    }
    cout<<sum<<"\n";
}

 

원래 처음엔 이분 탐색과 외에 맵을 사용하여 푸는것도 고려를 해보았는데 메모리 초과가 날 것 같아서 이분탐색 코드를 제출 한 후에 맵사용한 코드역시 제출해보았는데 예상대로 메모리 초과가 났다.