[백준] 8983번 - 사냥꾼 (파이썬)

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

# 사냥꾼

import sys
input = sys.stdin.readline
M, N, L = map(int, input().split())
shots_place = list(map(int, input().split()))
animals_place = []
for i in range(N):
    a, b = map(int, input().split())
    animals_place.append((a, b))

answer = 0
shots_place.sort()
for a, b in animals_place:
    start, end = 0, len(shots_place)-1
    mid = 0
    while start < end:
        mid = (start+end)//2
        if shots_place[mid] < a:
            start = mid + 1
        elif shots_place[mid] > a:
            end = mid - 1
        else:
            start = mid
            break
    if abs(shots_place[start]-a)+b <= L:
        answer += 1
    elif start+1 < len(shots_place) and abs(shots_place[start+1]-a)+b <= L:
        answer += 1
    elif start > 0 and abs(shots_place[start-1]-a)+b <= L:
        answer += 1
print(answer)

 

이분탐색
1. 사냥꾼의 위치 정렬
2. 동물의 위치 완전 탐색
    - 해당 동물의 위치에서 가장 가까운 사냥꾼의 위치를 이분탐색
    - 사냥꾼의 위치, 사냥꾼의 왼쪽 위치, 사냥꾼의 오른쪽 위치와 동물 사이의 거리가 L이하이면 answer += 1
3. answer 출력

 

아이디어 : 각 동물의 위치에서 가장 가까운 사냥꾼의 위치를 찾고 사정거리 내인지 확인

사냥꾼의 위치는 정렬을 하여 이분탐색 가능

각 동물의 위치에서 가장 가까운 사냥꾼의 위치 : a좌표가 같을 경우

a좌표가 다르면서 이분탐색이 끝날 경우가 있으니 현재 사냥꾼의 위치 전후로 L과 비교해주어야한다.