[알고리즘] 백준 8983 사냥꾼

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

최대 10만개의 사대와 10만 마리의 동물이 주어졌기 때문에, 완전탐색으로는 주어진 1초안에 끝내기 어려운 문제였다.

처음에는 각 사대의 최대 동물 수를 잡는 문제라고 읽고, 접근조차 못하고 있었다..

문제는 이진탐색을 이용하여 모든 사대를 합쳐서 잡을 수 있는 동물 수 카운트하여 출력하는 문제였다.

import sys

M, N, L = map(int, sys.stdin.readline().split())
shoot_pos = list(map(int,sys.stdin.readline().split())) # 사대 입력 받음
shoot_pos.sort() # 이진 탐색 대상이 사대 이므로, 오름차순으로 정렬

# 동물들의 위치 저장
animal_pos = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

result = 0
# 각 동물들의 위치에서 사대를 탐색한다.
# 사격 범위 |x - a| + b <= L 에 해당될 경우 해당 동물에 대해서 result += 1을 진행하고,
# 카운트를 했으므로, 해당 동물에 대한 사대의 이진 탐색을 종료한다.
for a, b in animal_pos:
    lt = 0 # 사대 시작 인덱스
    rt = len(shoot_pos) - 1 # 사대 끝 인덱스
    forward_range = a + b - L # 해당 동물을 잡을 수 있는 범위의 최솟값
    behind_range = a - b + L # 해당 동물을 잡을 수 있는 범위의 최댓값 

    while lt <= rt:
        mid = (lt + rt) // 2
        # 탐색중인 사대의 위치가 동물을 잡을 수 있는 사대 범위에 포함된다면 카운트
        if forward_range <= shoot_pos[mid] <= behind_range:
            result += 1
            break
        elif forward_range > shoot_pos[mid]:
            lt = mid + 1
        elif behind_range < shoot_pos[mid]:
            rt = mid - 1

print(result)

코드로 보면 이해가 쉬웠는데, 동물을 기준으로 반복문을 돌려 그 안에서 이진탐색을 진행한다는 아이디어와 해당 동물의 위치로부터 사냥 가능한 사대의 위치를 뽑아내는 부분을 떠올리는것이 쉽지 않았다.

과정을 요약해보면 다음과 같다.
1. 동물 위치를 기준으로 사대 위치에 대한 이진 탐색을 진행한다.
2. 동물 위치로부터 해당 동물 사냥이 가능한 사대의 위치 범위를 찾아낸다.
3. 이진 탐색을 통해, 해당 동물을 잡을 수 있는 사대가 탐색에 성공할 경우 해당 동물을 잡은것으로 간주하고 카운트를 하고, 해당 동물에 대한 사대의 이진 탐색을 종료한다.