7453번-합이 0인 네 정수

문제

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

7453번: 합이 0인 네 정수

---

접근방법

1) 접근 사고

주어진 배열이 4개이고 탐색을 해야 하는 문제이므로 2개의 배열씩 짝지어서 n^2으로 조합을 맞춘 뒤에 문제에서 주어진 조건이 a, b, c, d의 배열 4개의 합이 0이어야 하므로 더한 배열에서 이분 탐색을 실시하면 되는 문제였습니다.

 

2) 시간 복잡도

가장 단순하게 4개의 배열이니까 n^4으로 문제를 풀면 n은 4000이고 N의 4승이므로 64,000,000,000,000번의 연산이 일어나므로  10만억의 연산이 일어난다. 그 결과 100,000초 정도 걸리게 되고 문제에서는 12초만 주어지므로 시간 초과가 발생하게 되므로 logN의 알고리즘으로 줄여야 합니다.

 

3) 배운 점

https://blog.naver.com/jinhan814/222111197428 에서 코드를 참조하여서 풀었는데 equal_range라는 STL을 처음으로 배웠습니다. lower_bound와 upper_bound의 리런 값을 pair형으로 반환을 하여 준다는 STL인데 이런 식으로 탐색 값의 앞의 위치와 뒤의 값이 필요할 때 자주 쓸 거 같은 라이브러리인 거 같습니다.

 

4) PS

코드가 전반적으로 간단해서 이해하기 쉬울 거 같은데 이해가 안 가는 코드가 생긴다면 35번째 줄에서 이해가 안 갈 거라고 예상을 합니다. 이 코드는 c, d의 덧셈 조합 v에서 a, b의 조합을 탐색해서 그 위치의 앞과 뒤를 반환하는 코드입니다. lower_bound의 탐색 범위가 v[i-1] < mid < v[i]이기 때문에 탐색값중 가장 작은것을 반환하고 upper_bound의 탐색 범위는 v[i - 1] < mid <= v[i] 이기 때문에 반환 값의 다음 자리를 가리키게 됩니다. 이 문제에서 생길 수 있는 경우의 예시로 v조합의 값 중 하나가 10이라면 a + b의 배열 조합에서는 -10이 나와야만 합니다. 이때 -10을 성공적으로 가리키게 되면 lower_bound가 -10의 위치를 가리키게 되고 upper_bound가 -10의 다음 위치를 가리키게 되어 1을 더해줍니다. 만약 -10을 찾지 못한다면 똑같은 위치를 반환하기 때문에 high -low = 0이 되어 cnt 하지 않습니다. 밑에는 문제의 예제에서 탐색을 성공하는 경우입니다.

 

high는 29 low는 28 high - low = 1
high는 4 low는 3 high - low = 1
high는 16 low는 15 high - low = 1
high는 14 low는 13 high - low = 1
high는 30 low는 29 high - low = 1

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 4000;
int n;
vector<ll> a, b, c, d;
vector<ll> v;
int main(void)
{
    fastio;
    cin >> n;
 
    a.resize(n), b.resize(n), c.resize(n), d.resize(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++)
            v.push_back(c[i] + d[j]);
 
    sort(v.begin(), v.end());
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            auto cur = a[i] + b[j];
            auto [low, high] = equal_range(v.begin(), v.end(), -cur);
            ans += high - low;
        }
    }
    cout << ans << "\n";
}