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