백준 3151 (합이 0) - java

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

3151번: 합이 0

이진 탐색을 응용한 문제이다. 2개의 수를 선정하고 해당 합을 target으로 하여 총 합이 0이 되게 하는 하나의 수를 이진 탐색으로 찾는 문제이다. 

-> 중복을 허용하기 때문에 upper_bound, lower_bound를 응용해야 한다.

import java.io.*;
import java.util.*;
public class Main {
    static int n = 0;
    static int[] board;

    static long result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        board = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0;i<n;i++)
        {
            board[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(board); // 이진 탐색을 위한 정렬

        bs();
        System.out.println(result);
        br.close();
    }
    static int change(int num1)
    {
        return num1 * -1; // 합이 0이 되는 수를 구하는 함수
    }
    static void bs()
    {
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int idx1 = lower(j+1,n-1,change(board[i]+board[j]));
                int idx2 = upper(j+1,n-1,change(board[i]+board[j]));
                result += (idx2 - idx1); // 중복을 허융하기 때문에 lower, upper 사용
            }
        }

    }

    static int lower(int left,int right,int target)
    {
        while(left <= right)
        {
            int mid = (left + right) / 2;

            if(board[mid]<target)
            {
                left = mid + 1;
            }

            else{
                right = mid - 1;
            }
        }

        return left;
    }

    static int upper(int left,int right,int target)
    {
        while(left <= right)
        {
            int mid = (left + right) /2;

            if(board[mid] <= target)
            {
                left = mid + 1;
            }

            else{
                right = mid -1;
            }
        }

        return left;
    }
}