백준 #7453 / 합이 0인 네 정수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	2878	460	297	17.753%

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절대값은 최대 2²⁸이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

---

솔직히 이 문제는 잘 몰라서 다 뒤져봤다... 근데 Binary Search에서 Upper Bound와 Lower Bound에 대한 것을 하나 얻었다.

만족한다...ㅜㅠ

[How To Solve?]

- A, B, C ,D 를 모두 더해서 0인 값을 찾으면 좋겠지만, 그렇게하면 O(n^4)의 시간복잡도를 갖는다. 최악이다.

- 최대한 배열의 갯수를 줄여야한다. A와 B가 N개의 원소를 갖고 있다면 합쳐서 N^2개의 AB배열로 만든다.

- 만들어진 AB배열의 모든 원소를 기준으로 잡고, 정렬된 CD배열에서 Binary_Search로 절대 값은 갖고 부호가 다른 값을 찾는다.

- N*N번 반복해준다.

- 이때 Upper Bound, Lower Bound를 찾아서, 그 차이를 갯수에 축적시켜준다.

- 그 이유는, AB배열에서 -40이라는 값을 찾았다면, CD배열에서 40이라는 값을 찾았을 때, 갯수를 늘려주면 되는데

- 여기서 40이라는 값이 5개인 경우, BS를 5번이나 반복해야한다.

- 하지만 상한선(Upper Bound)과 하한선(Lower Bound)를 찾아준다면, 그 갯수의 차이를 축적시킴으로써

- 탐색으로 낭비되는 시간을 줄일 수 있다. 최적화가 가능하다는 의미.

[Code]

// boj.kr/7453
#include<iostream>
#include<algorithm>
#define MAX_SIZE 4001
using namespace std;
 
long long AB[MAX_SIZE * MAX_SIZE], CD[MAX_SIZE * MAX_SIZE];
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
 
    long A[MAX_SIZE] = { 0, };
    long B[MAX_SIZE] = { 0, };
    long C[MAX_SIZE] = { 0, };
    long D[MAX_SIZE] = { 0, };
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> A[i] >> B[i] >> C[i] >> D[i];
 
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            AB[idx] = A[i] + B[j];
            CD[idx++] = C[i] + D[j];
        }
    }
    sort(CD, CD + N*N);    // BS로 찾을 기준 배열만 정렬.
    
    long long cnt = 0;
    long left = 0, right = N*N;
 
    for (int i = 0; i < N * N; i++) {    // AB배열의 처음부터 N*N번째까지 BS로 쌍을 찾는다.
 
        while (left < right) {
            long long mid = (left + right) / 2;
            if (AB[i] + CD[mid] < 0) left = mid + 1;
            else right = mid;
        }
        long lower_bound = right;
        left = 0, right = N*N;
 
        while (left < right) {
            long long mid = (left + right) / 2;
 
            if (AB[i] + CD[mid] <= 0) left = mid + 1;
            else right = mid;
        }
        long upper_bound = right;
 
        cnt += upper_bound - lower_bound;
        left = 0, right = N*N;
    }
    printf("%lld\n", cnt);
    return 0;
}

// 주석

- 보통 BS에서 mid를 기준으로 값이 크면 left = mid+1, 작으면 right = mid-1로 옮겨간다.

- 하지만 여기서는 upper bound, lower bound를 찾는 것이 목표이므로 옮겨가지 않는다.

- 첫 번째 while문에서는 위에서 든 예처럼, 40보다 작지만 40보단 크지 않은 최대 정수를 찾으면, 그 값을 lower bound

- 두 번째 while문에서는 40 중에서 가장 큰 값을 찾아서 upper bound로 설정.

- 중복을 고려해야하는 문제는 BS로 Upper, Lower Bound 설정하는 스킬을 잘 이용할 줄 알아야겠다.