[Algorithm🧬] 백준 8983 : 사냥꾼

문제

역시.. 전체 탐색 말곤 감이 안와서 풀이 참고해서 풀었는데 이분 탐색인거 진심 감도 안왔음..........

아무튼 다른 풀이를 참고하여 동물 하나하나를 기준으로 해당 동물을 맞출 수 있는 사대를 찾았다.
1. 사대와 동물과 거리가 L (사격 거리) 이하임 : 맞출 수 있으므로 통과
2. 사대가 동물의 x 좌표보다 왼쪽에 있음 -> 오른쪽 사대 중 맞출 수 있는걸 찾아서
3. 사대가 동물의 x 좌표보다 오른쪽에 있음 -> 왼쪽 사대 중 맞출 수 있는걸 찾아서.

import sys

def dist(사대, 동물):
    return abs(동물[0] - 사대) + 동물[1]


readl = sys.stdin.readline

M, N, L = map(int, readl().split())
사대들 = list(map(int, readl().split()))
동물들 = [list(map(int, readl().split())) for _ in range(N)]

sum = 0


left = 0
right = M - 1

사대들.sort()

for 동물 in 동물들:
    left = 0
    right = M - 1

    while left <= right:
        mid = (left + right) // 2

		# 1
        if dist(사대들[mid], 동물) <= L:
            sum += 1
            break
        # 2
        elif 사대들[mid] <= 동물[0]:
            left = mid + 1
        # 3
        elif 사대들[mid] > 동물[0]:
            right = mid - 1


print(sum)