[BOJ 7453] 합이 0인 네 정수

문제 출처 : https://www.acmicpc.net/problem/7453

 

풀이 :

 

네 정수의 합을 0으로 만드는 문제입니다.

이 문제는 [BOJ 16287] Parcel (ICPC 2018) 과 비슷한 개념을 사용하여 풀면 됩니다.

a,b의 합을 ab라는 배열로 묶고, c,d의 합을 cd라는 배열로 묶어서 각각 정렬한다음

ab를 기준으로 cd중 -ab와 같은 값을 이분탐색을 통해 찾으면 됩니다.

저는 어퍼바운드를 구현하여 끝에서부터 내려오면서 중복 체크를했습니다.

ab의 값이 같다면 계산을 생략해주어야 시간초과가 나지 않습니다.

 

해쉬로도 풀수있는거 같으니 다음에 한번 풀어보겠습니다.

 

#include<stdio.h>
int n, a[4000], b[4000], c[4000], d[4000], ab[16000000], cd[16000000], sort[16000000],tmp;
long long int ret;
 
void mergesort(int l, int r,int *arr) {
    if (l >= r)return;
    int mid = (l + r + 1) / 2;
    int ll = l, rr = mid, cnt = l;
    while (ll<mid&&rr<=r) {
        if (arr[ll] > arr[rr])sort[cnt++] = arr[rr++];
        else sort[cnt++] = arr[ll++];
    }
    while (ll < mid)sort[cnt++] = arr[ll++];
    while (rr <= r)sort[cnt++] = arr[rr++];
    for (int i = l; i < cnt; i++)arr[i] = sort[i];
}
 
void merge(int l, int r,int *arr) {
    if (l >= r)return;
    int mid = (l + r + 1) / 2;
    merge(l, mid - 1,arr);
    merge(mid, r,arr);
    mergesort(l, r,arr);
}
 
int main() {
    scanf("%d", &n);
    for (int j = 0; j < n; j++)scanf("%d %d %d %d", &a[j], &b[j], &c[j], &d[j]);
    for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
        ab[i*n + j] = a[i] + b[j];
        cd[i*n + j] = c[i] + d[j];
    }
    merge(0, n*n - 1, ab);
    merge(0, n*n - 1, cd);
    for (int i = 0; i < n*n; i++) {
        if (i>0&&ab[i] == ab[i - 1]) {
            ret += tmp;
            continue;
        }
        int l = 0, r = n * n - 1, comp = ab[i] * -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (cd[mid] <= comp)l = mid + 1;
            else r = mid - 1;
        }
        if (cd[r] == comp) {
            tmp = 0;
            tmp++;
            for (int j = r; j > 0 && cd[j] == cd[j - 1]; j--)tmp++;
            ret += tmp;
        }
        else tmp = 0;
    }
    printf("%lld", ret);
}