8983. 사냥꾼

문제링크

난이도	정답률(_%)
Gold IV	29.165%

메모리 (KB)	시간 (ms)
141384	536

설계

처음에 잘못된 설계로 계속 애먹다가 결국 블로그에서 로직에 대한 힌트를 얻었습니다.ㅠㅠ
핵심 로직은 모든 사대가 모든 동물들을 검사하는 대신 각 동물의 가장 가까운 양쪽의 사대를 이분탐색으로 찾아 사냥할 수 있는지 확인하는 것입니다.

1. 사대와 동물들의 좌표를 입력받아 upper bound를 위해 둘다 x좌표를 기준으로 오름차순 정렬한다.
2. 동물들에 대해 for문을 돌면서 lower bound를 통해 가장 가까운 양쪽의 사대를 찾는다.
3. 양쪽의 사대에서 사격이 가능한 동물일 경우 ans 에 1을 더한다.

코드

m, n, l = map(int, input().split())
shooters = list(map(int, input().split()))
animals = []
for _ in range(n):
    x, y = map(int, input().split())
    if y <= l:
        animals.append((x, y))
shooters.sort()
animals.sort(key=lambda axis: axis[0])
ans = 0
idx = 0
for i in range(len(animals)):
    left, right = idx, len(shooters)-1
    mid = 0
    while left <= right:
        mid = (left+right)//2
        if shooters[mid] <= animals[i][0]:
            if len(shooters) - 1 == mid or shooters[mid+1] > animals[i][0]:
                break
            left = mid + 1
        else:
            right = mid - 1
    idx = mid
    if abs(animals[i][0] - shooters[mid]) + animals[i][1] <= l:
        ans += 1
    elif len(shooters) > mid+1 and abs(animals[i][0] - shooters[mid+1]) + animals[i][1] <= l:
        ans += 1
print(ans)

시간복잡도

O(N * logM)