[복기] 8983번: 사냥꾼

문제

백준 8983번: 사냥꾼

복기

처음 문제를 읽고 '이게 왜 이분탐색 문제지?'라고 생각했다. 단순무식하게 사대 M개와 동물의 수 N마리의 경우를 모두 계산해서 풀면 풀리기는 하겠지만, 애초에 시간초과가 날 것이 당연하고 그런 단순한 방법으로 풀어야할 문제도 아닐 것 같았다. 그러다 갑자기 번뜩여서 갈피를 잡고 코딩했다.

하나의 동물에게는 가장 가까운 사대 하나만 있으면 되므로, 동물의 x좌표와 가장 가까운 사대를 찾기위해 이분탐색을 돌린다. 이것을 모든 동물에게 반복하면 된다. 시간을 단축하려면 동물의 y좌표가 사정거리보다 길면, 계산하지 않고 건너뛰는 방법도 있다.

코드

import sys
input = sys.stdin.readline

m, n, l = map(int, input().split())
sade = list(map(int, input().split()))
sade.sort()

def bsearch(left, right, target):
    while left <= right:
        mid = (left+right)//2
        if sade[mid] < target:
            left = mid+1
        elif sade[mid] > target:
            right = mid-1
        else:
            return mid
    return right

answer = 0
for _ in range(n):
    x, y = map(int, input().split())
    if y > l:
        continue
    idx = bsearch(0, m-1, x)
    for k in [idx-1, idx, idx+1]:
        if 0 <= k and k < m:
            if y + abs(sade[k]-x) <= l:
                answer += 1
                break

print(answer)