백준 7453 - 합이 0인 네 정수

1. 문제 정리
  - 길이가 n인 네개의 배열 A, B, C, D가 주어진다.

  - 각 배열의 A[a], B[b], C[c], D[d] 값의 합이 0이 되는 경우의 수를 출력한다.

  - 배열에 입력 되는 정수의 최대값은 2^28이다.
 
2. 접근
  - 이분탐색으로 풀고자 하였다.

  - 먼저 A, B 배열의 모든 합의 경우의 수를 구하고, C, D 배열의 모든 합의 경우의 수를 구해, 마지막에 그 둘의 합이 0이 되는 경우의 수를 구한다.
 
3. 풀이

//2022.01.17
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
long long a[2][4001];
long long c[2][4001];
vector<long long> ab;
vector<long long> cd;

void go(long long arr[2][4001], vector<long long> &x){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            x.push_back(arr[0][i]+arr[1][j]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[0][i] >> a[1][i] >> c[0][i] >> c[1][i];
    }

    dfs(a, ab);
    dfs(c, cd);
    sort(ab.begin(), ab.end());

    long long ans = 0;
    for(long long i: cd){
        auto up = upper_bound(ab.begin(), ab.end(), i*(-1));
        auto low = lower_bound(ab.begin(), ab.end(), i*(-1));
        ans += up - low;
    }

    cout << ans;
}

  - long long a, c[2][4001] : a[0]에는 A, a[1]에는 B를, c[0]에는 C, c[1]에는 D 배열을 저장한다.

  - vector<long long> ab, cd : ab에는 A배열과 B배열의 모든 합을, cd에는 C배열과 D배열의 모든 합을 저장한다.

  - void go(long long arr[2][4001], vector<long long> &x) : arr[0] 배열과 arr[1] 배열의 모든 합을 x 벡터에 저장한다.

  - int main() : sort(ab.begin(), ab.end()) : ab 배열을 오름차순으로 정렬하여 이후 upper_bound, lower_bound를 사용할 수 있도록 해준다. 그 후 for loop 에서 cd를 순회하여 ab 벡터와의 합이 0이 되는 값을 이분탐색으로 찾고, upper_bound 인덱스와 lower_bound 인덱스의 차 값을 ans에 더해주어 경우의 수를 더해간다.

4. 소감

 이전에 푼 1208처럼 이분탐색을 통해 문제를 풀었다. 먼저 시간복잡도 상으로 나이브하게 4개의 값을 더해가면서 풀면은 시간 초과가 발생하기 때문에 4개의 배열을 2개씩 나누어 각 나타낼 수 있는 합을 모두 나타낸 뒤, 처리하도록 하였다.

 1208 문제를 처음 봤을 때처럽 답답하지는 않았다. 이전에 비슷한 유형의 문제(심지어 이번보다 어려웠다..)를 마주했던 게 큰 도움이 되었다 생각한다.

 하지만 아직 완전히 내 것으로 만들지는 못 한것 같아 살짝의 아쉬움도 남는 문제였다.