백준) 7453 합이 0인 네 정수

합이 0인 네 정수

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

크기가 N으로 같은 정수형 배열 네 개가 주어질 때,

각 배열의 원소를 하나 씩 골라서 더했을 때 0을 만들 수 있는 경우가 얼마나 되는지 계산해야 한다.

모든 경우를 시도해보고 0인 가짓수를 세 보면 가능하지만, 

N이 최대 사천이므로 N^4 으로 시간초과가 날 것이므로, 불가능함이 자명한 경우를 추리는 최적화가 필요하다.

예를 들어 세 정수의 합이 300 인데, 나머지 한 배열의 원소 중에 임의의 수를 더해봤더니 0보다 작다면,

그 수보다 작은 원소들은 시도해볼 필요가 없다.

따라서 이분 탐색을 통해 시간복잡도를 줄이기로 한다.

세 배열을 모두 더해보고 남은 한 배열에서 찾는다면 4000^3의 계산과정이 필요하다.

하지만 두 배열 씩 더해서 새로운 배열 두 개를 만들고, 한쪽 배열의 모든 원소를 다른 배열에서 이분탐색한다면,

새로운 배열 생성에 2 * 4000 ^ 2 만큼 걸리고, 남은 이분 탐색에선 4000 ^ 2 * log (4000 ^ 2) 만큼 걸린다.

주의할 점은, 중복의 경우를 세야 한다는 것이다.

예를 들어 한 쪽 배열에서 -40이란 원소에 의해 다른 배열에서 40을 찾는 경우에, 40은 중복해서 존재할 수 있다.

 

찾는 값은 lower_bound와 upper_bound의 차이 만큼 중복으로 존재한다.

만약 두 함수의 결과에 차이가 없다면, 다음 원소의 탐색시엔 upper_bound부터 탐색해도 무방하다.

코드로 옮기자면 다음과 같다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, nn;
int ab[16000000], cd[16000000];
int a[4000], b[4000], c[4000], d[4000];
 
 
int main() {
    scanf("%d", &n);
    nn = n*n;
 
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ab[n*i + j] = -(a[i] + b[j]);
            cd[n*i + j] = c[i] + d[j];
        }
    }
 
    sort(cd, cd + nn);
 
    int left = 0, right = nn;
    long long ans = 0;
 
    for (int i = 0; i < nn; ++i) {
 
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] > cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int lo = right;
        //int lo2 = lower_bound(cd, cd + nn, ab[i]) - cd;
 
        left = 0, right = nn;
        
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] >= cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int hi = right;
        //int hi2 = upper_bound(cd, cd + nn, ab[i]) - cd;
 
        ans += (long long)(hi - lo);
 
        left = 0, right = nn;
    }
 
    printf("%lld", ans);
 
    return 0;
}