백준 8983 사냥꾼

백준 8983 사냥꾼

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

8983번: 사냥꾼

 

처음 이 문제를 봤을 때, 풀이 방법을 아예 모르겠어서 막막했었다.

여러번 반복해서 보니, 신기하게 풀린다.

 

접근방법

사대를 움직여 해당 동물을 죽일 수 있는지 살펴본다!

기준을 사대로 잡아야 한다!!

 

풀이

사대 길이와 |x-a| + b 길이 비교해 해당거리 내에 있으면 동물을 잡을 수 있고

없으면, 사대 위치를 조정해야 한다.

 

사대 위치는 무조건 사대 리스트 안에서만 움직일 수 있다.

즉, 사대 위치는 6,1,4,9 범위 내에 있을 수 있으므로 index로 조절해야 한다.

사대 위치는 정렬 시켜놔야 left ,right 조절할 수 있으므로 정렬한다.

 

그리고 단순하게 동물의 x축 위치가 사대보다 크면 사대를 오른쪽으로 이동

반대로 동물의 x축 위치가 사대의  x축 위치보다 작으면 사대를 왼쪽으로 이동 시켰다.

 

나의 코드

import sys
input = sys.stdin.readline

M, N, L = map(int, input().split(' '))

Ls = list(map(int, input().split(' ')))

animals = list(map(int, input().split(' ')) for _ in range(N))

# M = 4 # 사대
# N = 8 # 동물
# L = 4 # 사정거리

# Ls = [6,1,4,9]
Ls.sort()

# animals = [[7,2],[3,3],[4,5],[5,1],[2,2],[1,4],[8,4],[9,4]]

cnt = 0
for a, b in animals:
    left = 0
    right = len(Ls) - 1
    while left <= right:
        mid = (left + right) // 2

        if abs(Ls[mid] - a) + b > L:
            if Ls[mid] < a:
                left = mid + 1
            else:
                right = mid - 1
        
        else:
            cnt = cnt + 1
            break
    # print(f'a :{a}, b :{b}, cnt: {cnt}')

print(cnt)