소스코드

import sys
input = sys.stdin.readline

M,N,L = map(int, input().strip().split())
sadaes = list(map(int, input().strip().split()))
sadaes.sort() # 이분탐색 필수 전제 : 정렬된 상태

result = 0 # 잡을 수 있는 동물의 수

def binary_search_is_hunt(a,b):
	start_idx, end_idx = 0, len(sadaes) - 1
	
	# 아예 사정거리 바깥의 높이인 경우 -> 못 잡음
	if b > L:
		return 0
	
	while start_idx <= end_idx:
		mid_idx = (start_idx + end_idx) // 2
		
		# 사정거리 안쪽인 경우
		if (abs(sadaes[mid_idx] - a) + b) <= L:
			return 1
		else:
			# a 좌표 위치에 따라 좌/우 범위 좁히기
			if a < sadaes[mid_idx]:
				# 중앙값보다 동물의 x좌표가 왼쪽 -> 왼쪽으로 범위 좁히기
				end_idx = mid_idx - 1
			else:
				start_idx = mid_idx + 1
	
	return 0 # 못 잡는 경우

for _ in range(N):
	a,b = map(int, input().strip().split()) # 동물의 좌표
	result += binary_search_is_hunt(a,b)
	
print(result)
	

풀이

• 10^9(10억) 범위 정도 되면 자동반사처럼 이분탐색을 먼저 떠올려보는게 좋습니다(물론 항상은 아님).
• 동물의 위치가 제공될 때마다 사대의 끝과 끝 인덱스를 이용해서 범위를 설정하고 이를 이용해 이분탐색을 합니다.
  • 애시당초 b(높이)가 사정거리 바깥인 경우엔 그냥 0을 반환합니다.
  • 사정거리 안 쪽이라면 1을 반환해 결과에 반영합니다.
  • 이분탐색을 진행하고도 잡지 못했다면 0을 반환합니다.
• 결과를 출력하면 끝!!