b7453. 합이 0인 네정수

 

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

 

 

 

4 개의 배열 a,b,c,d 가 있을 때 N개의 원소의합이 0이되는 조합의 수를 찾는 문제다.

N의 범위가 4000 즉 4000*4000*4000*4000 을 하게되면 쉽게 풀수 있으나
시간복잡도 측면에서 시간초과가 날것이 분명하기에

풀이방법을 이분탐색을 이용하여 A,B의 배열에서 가능한 조합 16000000개와 

C,D의 배열에서 가능한 더한 조합 16000000개를 만들어 두조합의 합이 0이되는경우를

세기로 하였다.

 

AB의 배열에서가능한 조합 A와 CD의 배열에서 가능한 조합 B를 순회돌기전 

정렬을 통해 A,B배열을 오름차순으로 정렬하고 
A의 원소중 -31,-31,-31 처럼 중복되는 경우가 생기면 이를 upperbound lowerbound를 통해

중복 범위를 찾아 이분탐색 횟수를 줄이려 노력하였다.

 

upperbound와 lowerbound의 원리에대해서 잘 알게되고 응용력이 강화될수 있었던 문제였다.

 

 

 

 

import java.io.*;
import java.util.*;

public class Main {
    static int N;

    static int lowerBound(long target, long[] B) {
        int left = 0;
        int right = B.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target <= B[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    static int upperBound(long target, long[] B) {
        int left = 0;
        int right = B.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target < B[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        long[][] input = new long[4][N];
        long[] A = new long[N * N];
        long[] B = new long[N * N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            input[0][i] = Integer.parseInt(st.nextToken());
            input[1][i] = Integer.parseInt(st.nextToken());
            input[2][i] = Integer.parseInt(st.nextToken());
            input[3][i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                A[count] = input[0][i] + input[1][j];
                B[count++] = input[2][i] + input[3][j];
            }
        }

        Arrays.sort(A);
        Arrays.sort(B);

        long answer = 0;
        for (int i = 0; i < A.length; i++) {
            if (i > 0 && A[i] == A[i - 1]) continue;
            int leftA = lowerBound(A[i], A);
            int rightA = upperBound(A[i], A);
            int leftB = lowerBound(-A[i], B);
            int rightB = upperBound(-A[i], B);
            answer += (long)(rightA - leftA) * (rightB - leftB);
            i = rightA - 1;
        }
        System.out.println(answer);
    }
}