[BOJ_3151] 합이 0

설명

---

어떻게 접근할지는 대강 파악했으나 상세히 떠오르지 않아 블로그를 보고 푼 문제이다.

 

해당 코드는 2개의 지점을 먼저 잡아두고 10000*10000 이분 탐색으로 가능한 범위 내의 숫자들을 가져오는 코드이다.

 

이게 무슨 말이냐면

 

-1,-1,-1,-1,1,2,2,2,2,2,2,3 이런식으로 수열이 들어오면 만일 한 번 이분 탐색해서 찾으면 -1,-1 fix 값 빼고 left,right 지정 후 mid = (l+r)/2 으로 찾으면 당연히 그냥 가능한 수열중 딱 하나를 빠르게 찾을 뿐이다.... 이러면 안되고 lower boundary의 끝 부분과 지금 수열에서 가능한 부분인 [5 번째 인덱스 자리 부터 ~ 10 번째 인덱스 자리까지 탐색해야한다.] upper boundary의 끝을 알아내면 된다.

 

N이 10000이니 풀 수 있는 방법이다. 최대 5억번 돌 수 있으니 이를 유념해야 할 거 같다.

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int arr[];
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());

        arr = new int[N];

        tk = new StringTokenizer(in.readLine()," ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(tk.nextToken());
        }

        Arrays.sort(arr);

        long cnt = 0;

        for (int i = 0; i < N; i++){
            for (int j = i + 1; j < N; j++){
                int sum = arr[i] + arr[j];
                int l = j + 1;
                int r = N;
                int left = lower_bound(l,r,sum);
                int right = upper_bound(l,r,sum);
                cnt += right - left;
            }
        }
        System.out.println(cnt);
    }

    private static int lower_bound(int l, int r, int sum) {
        while(l < r){
            int mid = (l + r) / 2;
            if(sum + arr[mid] >= 0){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    private static int upper_bound(int l, int r, int sum) {
        while(l < r){
            int mid = (l + r) / 2;
            if(sum + arr[mid] > 0){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}

 

3151번: 합이 0