[PY] 8983 : 사냥꾼

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

뭔가 너무 헷갈렸다. 이게 코드에 반영을 하는데 뭔가 자꾸 시원찮게 들어갔다.
결국엔 검색하니 절댓값의 범위에 대한 오인 판단으로 인한 것 이었다. 아이디어는 답과 동일했다. 아 짜증ㄴ ㅏ

처음엔 문제가 잘 안 읽혔다. 하지만 문제가 안 읽히면 답도 못 구하는데 어찌 그러리.. 읽고 이해하는데만 시간을 굴리다보니 견적이 잡혔다.

1. 사대 갯수와 사대 위치 정보, 동물 마리수와 동물 위치 정보, 사정거리가 입력된다.
2. 사대 위치 정보는 정렬한다. 동물은 배열에 pair 형태 (즉, x y 가 온전히 담기게끔)로 담는다.
3. 모든 동물에 대한 정보가 담긴 배열에서 아이템 하나씩 순회하며 다음을 조사한다 :
   1. 동물의 위치와 사대의 위치에 대해 거리를 알아 볼 수 있는 식이 abs(사대의 위치 - 동물.X) + 동물.Y 로 주어진다.
   2. 이 식의 결과 값이 사정거리보다 같거나 작으면 잡을 수 있는 동물이라고 간주 할 수 있다.
      • 하지만 나는 사대의 위치를 특정하고 있진 않다.
        따라서, 해당 식을 완성 시킬 수 있는 사대의 위치를 내가 갖고 있느냐? 를 알아야한다.
   3. 알건 다 알았다. 사대의 범위는 방금 언급했던 소규모 식에서 찾아 볼 수 있다. abs를 풀면 사대의 위치는 이 두 범위 이내에 있다 :
      • 사정거리 >= abs(사대의 위치 - 동물.X) + 동물.Y
        •  사정거리 - 동물.Y >= abs(사대의 위치 - 동물.X)
        • 동물.X - (사정거리 - 동물.Y) <= 사대의 위치 <= 동물.X + (사정거리 - 동물.Y)
        •  이 범위를 걸고 이분 탐색을 진행하면 된다.

비록 코드화는 덜 했지만..

import sys

shootZoneCnt, animalCnt, shootRange = (map(int, sys.stdin.readline().strip().split()))
shootZoneLst = list(map(int, sys.stdin.readline().strip().split()))
shootZoneLst.sort()
ans = 0

animalLst = [list(map(int, sys.stdin.readline().split())) for _ in range(animalCnt)]

# 정식 식
    # 사대의 위치 x, 동물의 위치 (a, b) 일 때, 이 간의 거리는 | x - a | + b 로 계산한다.
    # 위의 식으로 나온 결과가 사정거리보다 작거나 같아야 한다.
    # 사정거리 >= | 사대 위치 - 동물.X | + 동물.Y
    # 사대 위치가 

    
for i, j in animalLst:
    lowVal = i + j - shootRange
    highVal = i - j + shootRange

    left = 0
    right = len(shootZoneLst) - 1

    while left <= right:
        mid = (left + right) // 2
        if(lowVal <= shootZoneLst[mid] <= highVal):
            ans += 1
            break
        elif lowVal > shootZoneLst[mid]:
            left = mid + 1
        elif highVal < shootZoneLst[mid]:
            right = mid - 1
            
print(ans)