[python] BOJ 8983 사냥꾼

[intro]

사냥꾼이라는 단어에 현혹되지 마십시오. 당신은 사냥감입니다.

생사의 기로에 놓인 한마리 토끼가 되어 보는게 문제의 핵심 키

⇒ 동물을 기준으로 내가 죽을 수 있는 범위의 x 좌표에 사대가 있는지를 확인하고, 그 사대에서 나를 맞출 수 있는 사격범위안에 들어오는지 계산한다. 만약 그 범위 안에 내가 있다면 나는 죽는다.

⇒ 왜 동물을 기준으로 생각해야 하는가?

동물을 기준으로 생각 : 100,000 log 100,000 = 500000 (동물의 수에 대한 이분탐색의 시간복잡도)

사대기준으로 생각 : 100,000 100,000 = 10,000,000,000 (사대의 수 동물의 수의 시간복잡도)

[코드 설명]

사대를 확인하는 과정에서 이분탐색을 사용하기 때문에 정렬 해준 다음 헌팅 함수에 유효한 start_x 범위와 end_x 범위를 찾는다.

⇒ 동물의 y 좌표가 총의 사정거리보다 크다면 잡을 수 없는 동물이므로 다음 좌표를 본다.

hunting 함수는 동물의 x,y좌표로 계산된 유효 사대의 시작과 끝을 받아 해당 범위 내에 사대가 존재하는지를 확인한다.

사대는 start ≤ candidate ≤ end 내에 존재해야 하며 이 범위에 존재하지 않는다면 사대는 없는 것, candidate의 초기값은 이 문제에서 들어올 수 없는 최댓값으로 설정해야 하므로 20억 1(10억 + 10억 + 1)로 설정한다.

리턴하는 값은 사대가 존재한다면 True, 존재하지 않는다면 False 이다. 이 과정에서 이분탐색이 사용된다.

def hunting(start, end):
    candidate = 2000000001
    left = 0
    right = len(hunting_zone) - 1
    while left <= right:
        mid = (left + right) // 2
        if start > hunting_zone[mid]:
            left = mid + 1

        else:
            right = mid - 1
            if candidate > hunting_zone[mid]:
                candidate = hunting_zone[mid]

    return candidate <= end


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

hunting_zone = list(map(int,input().split()))
hunting_zone.sort()
death = 0
for i in range(m):
    animal_x, animal_y = map(int, input().split())

    if animal_y <= l:
        start_x = animal_x - (l - animal_y)
        end_x = animal_x + (l - animal_y)

        if hunting(start_x, end_x):
            death = death + 1

print(death)