[Python 3] BOJ 8983 사냥꾼

오늘 풀어볼 문제는 '사냥꾼'이라는 문제이다.

 

알고리즘: binary search

 

서브태스크 문제란 문제의 input size나 특정 조건을 부여해서, ~~~한 상황일때, AC를 받는다를 확인할 수 있다. 백준에서 '맞았습니다!' 판정을 받기 위해서는, 모든 서브태스크, 즉 케이스를 통과해야 한다. 결국, '추가적인 제약 조건은 없다'의 40점어치를 맞춰야 결국 맞았습니다! 인 것이다.

 

우선, 문제에서는 총을 쏠 수 있는 사대들을 준다. 사대들에서 택시 거리로 L 만큼 떨어져있는 곳까지 총을 쏠 수 있다. 사대는 (X, 0)의 위치에 있기 때문에, 동물들과 사대의 x좌표를 비교해서, 동물과 제일 가까운 x좌표를 정한다. 바로 이 때, 동물의 수가 10만까지 가능하고, 사대의 개수가 10만개까지 있을 수 있기 때문에, 완전 탐색을 이용하면 100억개의 연산을 해야하고, 이는 무조건적인 TLE를 낼 것이다. 그렇기에, 특정 동물을 잡을 수 있는 사대를 정하기 위해 이분탐색을 이용한다.

m,n,l=map(int,input().split())
data=list(map(int,input().split()))
data.sort()
answer=0
for _ in range(n):
    x,y=map(int,input().split())
    left=0
    right=m-1
    mid=0
    while left<=right:
        mid=(left+right)//2
        if data[mid]==x:
            right=mid
            break
        elif data[mid]<x:
            left=mid+1
        else:
            right=mid-1
    dist=abs(x-data[right])+y
    if right+1<m:
        dist=min(dist,abs(x-data[right+1])+y)
    if dist<=l:
        answer+=1
print(answer)

 

먼저, 사대를 모두 input 받고, 정렬한다.

 

첫번째 사대를 left, 마지막 사대를 right이라고 설정하고, right이 left보다 작아질 때 까지 이분탐색을 실시한다.

만약 딱 mid일 때 사대가 위치하면, 이를 올바른 사대로 생각하여 처리한다.

하단에서는 두 사대에 대해서 비교하는데, 

right번째 사대가 이제는 오히려 왼쪽에 있는 사대이다.

즉, while문에서 나갔을 때,

 

right=4, 동물이 있는 x좌표 = 5, right+1 = 6 이런 식일 수 있다는 것이다.

right으로 뽑은 인덱스가 무조건적으로 동물과 제일 같다는 건 보장이 되지 않고,

동물이 있는 x좌표보다 작거나 같다, 라는 의미이다.

즉, right=4, 동물이 있는 x좌표 = 1000, right+1=1001 인 경우,

right+1의 x좌표가 동물이 있는 x좌표와 훨씬 가깝기 때문에, 이를 이용해야 할 것이다.

결국 택시거리를 구해서, 사대와 동물의 택시거리가 l 이하이면 answer+=1 한다.