[이분탐색] 백준 8983번 사냥꾼 with Python3 ★

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

8983번: 사냥꾼

문제

 

내 풀이

import sys
input = sys.stdin.readline

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

# 동물을 기준으로 자신을 죽일 수 있는 사대가 있는지를 이분 탐색했다.
# 있을 경우 count가 올라간다.

count = 0
for _ in range(n):
    x, y = map(int, input().split())

    left = 0
    right = len(shootpos)-1
    # print(x, y)

    # 이분 탐색
    if l >= y:

        while left <= right:
            inix = 0
            mid = (left + right) // 2
            inix = shootpos[mid]
            
            if (y <= l and inix-l <= x <= inix + l) and (x - (inix-l) >= y and x - inix + y <= l):
                # x, y가 뾰족한 이등변 삼각형 안에 잘 들어와있는지 체크. 기본적으로 0,0좌표로 옮기고 eg(-inix) 조건을 줬다.

				count += 1
                break

            if x >= inix:
                left = mid + 1

            else:
                right = mid - 1


print(count)

해설

풀이 개념은 조언을 참고하고 구현은 전부 직접했다.

 

생각보다는 쉬운 문제였는데, 시간이 걸리는 부분은 좌표가 사대 사거리 내에 있는지 없는지를 판명하는 조건이었다.

 

사실 좀만 잘 생각했으면 금방 떠올릴 수 있었는데, 아무튼 삼각형의 왼쪽 반은 x >y일때임을 쉽게 알았는데, 반대 쪽 반은 y+x <= L 보다 작을 때임이 잘 생각나지 않았다. 

 

중학교 때 마름모 도형 그래프 그리기 같은 걸로 했었을 텐데... 이 절망적 수학능력...

아무튼 조건 이외에는 이분탐색은 나무자르기와 같이 기본적인 이분탐색과 매우 유사했다고 본다.

 

정답 풀이

#내 답이 마음에 들어서 아직은 다른 답은 안찾아보겠다.

출처:

 

해석