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

문제 링크

• http://icpc.me/7453

문제 출처

• ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2005 E번

사용 알고리즘

• 이분탐색 unordered_map

풀이

4개의 배열이 주어지고, (a, b, c, d)의 합이 0이 되는 쌍의 갯수를 구해야합니다.

우선, 가장 navie하게 생각한다면 4번의 for문을 돌려 답을 찾는 방법이 있겠습니다.

하지만, N의 최대가 4000이므로 시간 복잡도 O(N^4)로 시간 초과가 발생할 게 분명해보입니다.



그렇다면, 기본적으로 4개의 배열을 A, B 배열의 합, C, D 배열의 합으로 구성된 2개의 배열로 나누어 생각해봅시다.

이후, 해당 문제를 푸는 2가지 방법이 존재합니다.

첫번째, 이분탐색을 하는 방법입니다.

이분탐색을 구현하는 여러 방법이 있겠지만, C++ STL인 lower_bound와 upper_bound를 활용하면 쉽게 구현이 가능합니다.

lower_bound를 통해 절댓값은 일치하되, 부호가 다른 값을 구해줍니다.

여기서, upper_bound를 사용하는 이유는 같은 값이 여러개 나올 수 있기 때문입니다.

설명하자면, lower_bound는 크기가 같거나 작은 값의 인덱스를 반환하는 데, 동일한 값이 여러개라 하더라도 처음 만나게 되는 인덱스만을 반환하기 때문입니다.

그러므로, upper_bound를 통해 찾고자 하는 값보다 다음으로 큰 값의 인덱스를 찾아 인덱스의 차이를 구함으로서 같은 값의 갯수를 세어주어야 합니다.

• 이분탐색을 위해서는 반드시 정렬이 되어있어야 합니다.

두번째, unordered_map 자료구조를 활용하는 방법입니다.

백준에서 다른 분들의 풀이를 둘러보는 중, cozyyg님의 map 자료구조를 통한 풀이가 인상깊었습니다.

나누어진 두 배열 중, 하나의 배열의 값을 map의 key값에 저장하여, 카운팅해줍니다.

이후, 마찬가지로 나머지 배열에서 절댓값은 같고, 부호만 다른 값이 map에 카운팅되어있다면, 정답에 더해주는 방식입니다.

이분탐색 코드

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INFL 2e18
#define INF 1e9


int main() {
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    vector<ll> A(n), B(n), C(n), D(n);
    for(int i=0; i<n; i++) {
        ll a, b, c, d; cin >> a >> b >> c >> d;
        A[i] = a; B[i] = b; C[i] = c; D[i] = d;
    }
    vector<ll> AB, CD;
    ll cnt = 0;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            ll res = A[i] + B[j];
            AB.push_back(res);
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            ll res = C[i] + D[j];
            CD.push_back(res);
        }
    }

    sort(AB.begin(), AB.end());
    sort(CD.begin(), CD.end());

    // 같은 값이 여러개일 경우, 갯수를 세줘야하므로 upper_bound를 사용한다.
    for(int i=0; i<AB.size(); i++) {
        ll preCD = lower_bound(CD.begin(), CD.end(), -AB[i]) - CD.begin();
        ll refCD = upper_bound(CD.begin(), CD.end(), -AB[i]) - CD.begin();

        if(AB[i] + CD[preCD] == 0) {
            cnt += refCD - preCD;
        }
    }

    cout << cnt;
}

unordered_map 코드

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INFL 2e18
#define INF 1e9

unordered_map<ll, ll> mp;
ll ans;

int main(){
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;

    vector<ll> a(n), b(n), c(n), d(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++) {
            ll x = a[i] + b[j];
            if(!mp.count(x)) mp[x] = 0;
            mp[x]++;
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            ll x = -(c[i] + d[j]);
            if(mp.count(x)) {
                ans += mp[x];
            }
        }
    }
    cout << ans;

}