[백준 / Python] 8983 사냥꾼

문제 링크

https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

---

 

코드

from bisect import bisect_left
input = __import__('sys').stdin.readline
m,n,l = map(int,input().split())
people = sorted(list(map(int,input().split())))
cnt = 0
for _ in range(n):
    x,y = map(int,input().split())
    if y>l:continue
    nx = bisect_left(people,x)
    for idx in (nx,nx-1):
        if 0<=idx<m:
            if abs(people[idx]-x)+y<=l:
                cnt+=1
                break
print(cnt)

---

문제 풀이

처음에 사냥꾼의 입장에서 생각했을 때는 헛갈렸는데, 동물의 입장에서 생각하면 쉽게 접근할 수 있다.

동물의 위치에서 가장 가까운 사대의 위치가 사정거리 안이라면 count를 해준다.

가장 가까운 사대의 위치가 사정거리를 벗어나면 어떠한 사대에서도 그 동물을 잡을 수 없다.

y의 거리가 l(사정거리)보다 크면 애초에 사정거리에서 벗어나 잡을 수 없으므로 조건문을 걸어준다.

bisect_left를 이용하여 동물과 가장 가까운 사대의 위치를 찾는다.