[백준/JAVA] BOJ 8983 - 사냥꾼

이분탐색을 마스터 해 보자!! 💪

👀 문제

8983번: 사냥꾼 ✨ 골드 4

KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다.

사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다.

예를 들어, 아래의 그림과 같은 사냥터를 생각해 보자. (사대는 작은 사각형으로, 동물의 위치는 작은 원으로 표시되어 있다.) 사정거리 L이 4라고 하면, 점선으로 표시된 영역은 왼쪽에서 세 번째 사대에서 사냥이 가능한 영역이다.

사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오.

예제 입력

4 8 4
6 1 4 9
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4

예제 출력

6

🔑 키포인트

이분 탐색

✍️ 코드

🔥 사대와 동물 간의 거리에서 중요한 것은 x좌표

1️⃣ 사대 위치 오름차순 정렬해 주기
2️⃣ 각 동물의 위치에서 가장 가까운 사대 찾기 (이분 탐색 활용)
📍 이때, y좌표가 l보다 크다면 애초에 불가능한 거리이므로 바로 continue 처리 해 주었어요
3️⃣ 만약 사대와 동물 사이의 거리가 사정 거리 이내라면 answer++
4️⃣ 사대가 동물의 x 좌표보다 오른쪽에 위치해 있으면 end = mid - 1, 왼쪽에 위치해 있으면 start = mid + 1

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

public class BOJ8983_사냥꾼 {
    public static void main(String[] args) 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 l = Integer.parseInt(st.nextToken());
        int answer = 0;

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 이분탐색 위해서 오름차순 정렬

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (y > l) { // 애초에 y가 사정거리보다 큰 경우는 안 됨
                continue;
            }

            int s = 0;
            int e = n - 1;
            while (s <= e) {
                int mid = (s + e) / 2;
                int dist = Math.abs(arr[mid] - x) + y;

                if (dist <= l) {
                    answer++;
                    break;
                } else {
                    // 사대가 동물보다 왼쪽에 있으면
                    if (arr[mid] < x) {
                        s = mid + 1;
                    } else { // 사대가 동물보다 오른쪽에 있으면
                        e = mid - 1;
                    }
                }
            }
        }
        System.out.println(answer);
    }
}