[백준 7453] 합이 0인 네 정수 [C]

백준 - 7453

---

풀이

제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다.

때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다.

 

합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다.

qsort(AB, N, sizeof(int), compare);
qsort(CD, N, sizeof(int), compare);

long long cnt = 0;
for (int i = 0; i < n*n; i++){
    int left = 0, right = N, mid;
		
    while (left < right){
        mid = (left+right) / 2;
        if (CD[i]+AB[mid] > 0) right = mid;
        else left = mid + 1;
    }
    int temp = right;
		
    left = 0, right = temp;
    do{
        if (AB[mid]+CD[i] >= 0) right = mid;
        else left = mid + 1;
        mid = (left+right) / 2;
    }while (left < right);
		
    cnt += (temp - right);
}

upper bound에서 얻은 값은 lower bound값보다 같거나 크기 때문에, lower bound를 구할 때 이용하면 좀 더 빨리 값을 찾을 수 있다. 

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 4000
int AB[MAX*MAX], CD[MAX*MAX];
int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
int main(){
    int n;
    scanf("%d", &n);
    int A[n], B[n], C[n], D[n], N = 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[i*n+j] = A[i]+B[j];
            CD[i*n+j] = C[i]+D[j];
        }
		
    qsort(AB, N, sizeof(int), compare);
    qsort(CD, N, sizeof(int), compare);
	
    long long cnt = 0;
    for (int i = 0; i < N; i++){
        int left = 0, right = N, mid;
		
        while (left < right){
            mid = (left+right) / 2;
            if (AB[mid]+CD[i] > 0) right = mid;
            else left = mid + 1;
        }
        int temp = right;
		
        left = 0, mid = right;
        do{
            if (AB[mid]+CD[i] >= 0) right = mid;
            else left = mid + 1;
            mid = (left+right) / 2;
        }while (left < right);
		
        cnt += (temp - right);
    }
    printf("%lld", cnt);
}

---

출처

7453번: 합이 0인 네 정수