[백준] 8983번 : 사냥꾼

8983번: 사냥꾼

8983번: 사냥꾼

🤔 문제분석

이분탐색으로 문제를 해결하는것을 깨닫았으나, 어떻게 조건을 세워야할지 감을 못잡았습니다.

동물을 기준으로 L범위엔에 들어가는 사냥꾼을 찾아내고 L의 범위안에 들어왔을 경우만 카운팅 하면 된다. 범위를 계산하는 방법은 절대값의 수식에서 점화식을 도출 할 수 있다.

아래의 식에서 S와 E 범위안에 들어간다면 동물이 사냥꾼의 L범위안에 들어가게된다.

💻 코드

import sys
input = sys.stdin.readline

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

attack = list(map(int, input().split()))
animal = list(map(int, input().split()) for _ in range(N))
attack.sort()

ans = 0
for x, y in animal:
    if (y>L):
        continue
    
    s = x+y-L
    e = x-y+L
    start, end = 0, M-1
    while start <= end:
        mid = (start+end)//2
        if attack[mid] >= s and attack[mid] <= e:
            ans += 1
            break
        elif attack[mid] < e:
            start = mid + 1
        else:
            end = mid - 1
print(ans)

🎯 피드백 및 개선사항

이번주도 정렬문제를 푸는데 다양한 유형을 익혀서 스킬업이 되는 기분이다. 많은 문제를 풀어보고, 다른 사람들이 어떻게 풀었는지 참고하여 알고리즘을 잘해지고 싶다… 😀