백준 블랙홀과 소행성(29755)

 

이분 탐색 문제를 풀어 보았다.

 

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

29755번: 블랙홀과 소행성

 

 

문제의 공식의 최소값을 구하는 문제이다.

 

공식을 잘 살펴보 |b-a| 해당 부분이 작을수록 최소값을 가질수 있는 것으로 보인다.

 

해당 값이 결국 작으려면 블랙홀과 행성의 거리 차가 가장 짧은 것을 찾으면된다. 각 행성별로 거리 차이 * 무게가 가장 높은게 최소 P 값이라고 생각할 수 있겠다

 

일반 탐색을 사용하는경우 시간초과가 발생이 높아 블랙홀을 정렬후 이분탐색을 진행하면 된다.

 

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] hole = new int[N];
        int[] a = new int[M];
        int[] w = new int[M];

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


        for (int i=0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            w[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(hole);

        int answer = 0;

        for (int i=0; i < M ; i++) {
            answer = Math.max(Math.abs(binarySearch(hole, 0, N - 1, a[i]) - a[i]) * w[i], answer);
        }

        System.out.println(answer);
    }


    public static int binarySearch(int[] hole, int left, int right, int target) {

        while (left <= right) {

            int mid = (left +  right) / 2;

            if (hole[mid] == target) {
                return target;
            } else if (hole[mid] < target) {
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }

        if (left >= hole.length) {
            return hole[right];
        } else if (right < 0) {
            return hole[left];
        } else {
            int gap1 = Math.abs(target - hole[left]);
            int gap2 = Math.abs(target - hole[right]);
            return gap1 < gap2 ? hole[left] : hole[right];
        }
    }
}

 

결과