[BOJ] 백준 8983 사냥꾼

출처: https://www.acmicpc.net/problem/8983

Approach

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

① 모든 동물에 대해 사격가능한 사대가 있는지 완전 탐색하는 경우 TLE 발생 → O(N × M)

② 특정 사대에서 사격가능한 동물을 표시하는 방법

사대의 위치를 X 라고 했을 때, 좌우로 사격가능한 범위는 1차로 [X-L, X+L]입니다.

해당 구간에서도 문제에서 정의한 동물의 위치(a, b)일 때, |X-a| + b ≤ L에 해당하는 동물들 입니다.

이 경우에도 각 사대에 사격거리 내에 있는 동물의 수를 탐색해야 하기 때문에 TLE 발생

 

③ 동물의 입장에서 이분 탐색을 이용합니다.

    즉, 자신을 저격할 수 있는 사대를 찾는 것입니다.

Q) 자신을 저격할 수 있는 가장 확실한 사대의 위치는?

     → (x 좌표상) 자신과 가장 가까운 사대

자신의 x 위치를 기준으로 왼쪽에서 가장 가까운 사대를 찾습니다. 

→ Upper Bound (사대가 x좌표 기준으로 정렬되어야 합니다.)

Q) 오른쪽으로 기준으로 가장 가까운 사대를 어디일까?

→ 위에서 찾은 사대 다음으로 존재하는 사대입니다. 

    (x좌표 기준으로 정렬하였기 때문)

두 사대에서 사격가능 여부를 확인합니다. 

(두 개 실패인 경우 다른 사대에서도 저격할 수 없는 범위 입니다.)

 

구현 사항

동물들을 정렬할 필요는 없지만, 정렬해놓는다면 가장 가까운 사대를 이분 탐색할 때,

이전에 찾아놓은 사대 위치를 탐색 시작위치로 이용할 수 있습니다.

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int MAX_M = 100000;
const int MAX_N = 100000;
 
struct Item {
    int x, y;
    int isDead;
}gun[MAX_M + 1], animal[MAX_N + 1], copyArr[MAX_N + 1];
 
int M, N, L, ans;
inline int abs(int x) { if (x < 0) return -x; return x; }
inline int getDistance(Item weapon, Item target) {
    return abs(weapon.x - target.x) + target.y;
}
 
void mergeSort(Item*arr, int s, int e) {
    if (s >= e) return;
 
 
    int m = (s + e) / 2;
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
 
 
    int i = s, j = m + 1, k = s;
    while (i <= m && j <= e) {
        if (arr[i].x < arr[j].x) copyArr[k++] = arr[i++];
        else copyArr[k++] = arr[j++];
    }
    while (i <= m) copyArr[k++] = arr[i++];
    while (j <= e) copyArr[k++] = arr[j++];
 
 
    for (i = s; i <= e; ++i) {
        arr[i] = copyArr[i];
    }
}
 
int upper_bound(int pivot) {
    int low = 0, high = M - 1, ret = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (pivot >= gun[mid].x) {
            ret = mid;
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return ret;
}
 
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    // 사대, 동물의 수, 사정거리
    scanf("%d %d %d", &M, &N, &L);
 
 
    // 사대 위치
    for (int i = 0; i < M; ++i) {
        scanf("%d", &gun[i].x);
    }
    // 동물 위치
    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &animal[i].x, &animal[i].y);
        animal[i].isDead = 0;
    }
 
    mergeSort(gun, 0, M - 1);
    mergeSort(animal, 0, N - 1);
 
    for (int i = 0; i < N; ++i) {
        // 맞추고자 하는 동물 왼쪽에서 가장 가까운 사대 위치
        int left = upper_bound(animal[i].x);
        // 동물 왼쪽에 가장 가까운 사대가 존재할 때, 사격가능 여부 확인
        if (left != -1 && getDistance(gun[left], animal[i]) <= L) {
            ans++;
            animal[i].isDead = 1;
        }
 
 
        // 왼쪽에 가장 가까운 사대가 존재하지 않거나, 사정거리가 아닌 경우
        // 즉, 아직 동물이 죽지 않은 경우
        if (!animal[i].isDead) {
            // left가 존재하지 않은 경우(-1), right = 0 (첫번째 사대)
            int right = left + 1;
            // 동물에서 가장 가까운 오른쪽 사대가 존재하는 경우
            if (right < M && getDistance(gun[right], animal[i]) <= L) {
                ans++;
                animal[i].isDead = 1;
            }
        }
    }
 
 
    printf("%d\n", ans);
}