문제 링크

사냥꾼

문제 설명

N마리의 동물들을 일직선 상의 M개의 사대 위에서 사격하려고 한다. 사대의 좌표는 x1, x2, ..., xm으로 x축 위에 있고, 동물들은 (a1, b1), (a2, b2), ..., (an, bn)의 좌표 위에 있다. 총의 사정거리를 L이라고 할 때, |xi-aj|+bj <= L인 동물만 사격이 가능하다. 잡을 수 있는 동물 수는?

문제 풀이

시도 1

각 동물의 좌표 별 제일 가까운 사대를 찾기 위해서 사대를 대상으로 이분탐색을 했다.
파이썬 내장함수 bisect_left, bisect_right을 이용해서 동물의 x좌표가 오름차순으로 정렬된 사대 리스트에 들어갈 수 있는 인덱스를 찾았다.

l_idx = bisect_left(hunters, animal[0])
r_idx = bisect_right(hunters, animal[0])

bisect_left, bisect_right에서
i) 반환된 인덱스가 다르면
-> 동물이 위치한 x축 위에 사대가 있다는 뜻이므로 해당 사대가 제일 가까움
ii) 반환된 인덱스가 같으면
-> 동물이 위치한 x축위에 사대가 없으므로 반환된 인덱스와 그 인덱스의 앞을 비교해서 가장 가까운 사대를 찾는다.

if l_idx != r_idx:
  h = hunters[l_idx]
else:
  if l_idx == 0:
          h = hunters[l_idx]
  elif r_idx == M:
          h = hunters[r_idx-1]
  elif abs(hunters[l_idx-1]-animal[0]) < abs(hunters[l_idx]-animal[0]):
          h = hunters[l_idx-1]
      else:
          h = hunters[r_idx]

전체 코드

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

M, N, L = map(int, input().split())
hunters = list(map(int, input().split()))
hunters.sort()
animals = []
for _ in range(N):
    animals.append(list(map(int, input().split())))
animals.sort()
answer = 0

for animal in animals:
    l_idx = bisect_left(hunters, animal[0])
    r_idx = bisect_right(hunters, animal[0])
    h = 0
    if l_idx != r_idx:
        h = hunters[l_idx]
    else:
        if l_idx == 0:
            h = hunters[l_idx]
        elif r_idx == M:
            h = hunters[r_idx-1]
        elif abs(hunters[l_idx-1]-animal[0]) < abs(hunters[l_idx]-animal[0]):
            h = hunters[l_idx-1]
        else:
            h = hunters[r_idx]
    if abs(h-animal[0])+animal[1] <= L:
        answer += 1 
    
print(answer)

가장 가까운 사대를 탐색하는 부분에서 bisect 함수에 대한 이해가 부족하여 프린트로 한참 찍어보면서 풀었다,,^_^ 코드가 넘 더러워서 정답이 아닌 것 같음.. 낼 스터디에서 한번 보기로 ,,

시도 2

스터디에서 다른 분 풀이를 들었는데 출제자의 의도는 그분이 푸신 방법대로 풀라고 낸거같았다. 이분탐색의 대상을 사대로 두는데, 현재 사대에서 사격이 가능한지를 매번 검사하는 방법이었다.

import sys
input = sys.stdin.readline

M, N, L = map(int, input().split())
hunters = list(map(int, input().split()))
animals = []
for _ in range(N):
    animals.append(list(map(int, input().split())))

hunters.sort()
animals.sort()
answer = 0

for animal in animals:
    start, end = 0, len(hunters)-1
    while start <= end:
        mid = (start+end)//2
        dist = abs(hunters[mid]-animal[0])+animal[1]

        #해당 사대에서 사격 가능하면
        if dist <= L:
            answer += 1
            break
        else:
            if hunters[mid] < animal[0]:
                start = mid+1
            else:
                end = mid-1
print(answer)

이 풀이 말고도 사대의 범위별로 나누어서 계산하는 방법 등 여러 풀이를 들어보았다. 굿 ,,