땅! 땅! 땅! 빵! (백준 8983 : 사냥꾼)

8983번: 사냥꾼 (acmicpc.net)

8983번: 사냥꾼

 

많은 고민을 했던 문제이다.

처음에는 동물들의 좌표를 x축으로 정렬하고 각 x좌표마다 사거리를 계산해서 그 사거리 안에 있는 동물들을 탐색해봤는데, 아무리 시간을 좁혀봐도 시간초과가 났다.

 

그런데, 내 생각에 맹점이 있었다.

좌표값은 10억이기 때문에 x축을 기준으로 사거리를 계산하는 것은 엄청난 시간이 걸리는 반면, 동물의 수는 10만에 불과하다. (최댓값 기준)

그러면 각 동물들의 좌표를 기준으로 사로를 탐색하는 접근을 해야 시간을 단축할 수 있는 것이다.

심지어, 이것이 출제자의 의도인지 사거리는 가로 세로로만 움직인다. (얼마나 계산하기 편해지는지 아래를 보자!)

 

동물들의 좌표를 기준으로 사로를 탐색하는 법은 다음과 같다.

 

1. 사거리에서 동물 좌표 y값을 뺀다. (사로는 x축 위에만 있기 때문이다. 그렇기 때문에 우선 x축에 도달해야되서 사거리에서 y값을 뺀다.)

 

2. 그리고 해당 x좌표 ±남은 사거리 안에 사로가 있는지 탐색한다. (이 부분은 이분 탐색을 쓰면 시간이 단축될 것이다.)

 

이걸로 로직은 끝이다.

이리 간단한 걸, 왜 진작 생각하지 못했을까. 아직 많이 멀었다는 것을 느낀다.

 

 

이제 탐색 상세 로직을 만들어보자.

1. left_ptr = 0, right_ptr = len(base) - 1 로 지정하고, mid는 둘의 중간값으로 한다.

2. 중간 사로의 위치 (base[mid]) 가 사거리 내(min_base, max_base)에 있는지 판별하자.

3. 그리고 base[mid]가 사거리 왼쪽에 있다면 ( base[mid] < min_base ) left_ptr를 mid + 1 로 하고, 오른쪽에 있다면 right_ptr을 mid-1로 한다.

 

import sys

# M : 사대의 수
# N : 동물의 수
# L : 사거리
M, N, L = map(int,sys.stdin.readline().split())

# base = 사대 위치
base = list(map(int,sys.stdin.readline().split()))
base.sort()

# 사거리 안에 있는 동물의 수
count = 0

# 탐색 함수
def search(x, min_base, max_base):
    left_ptr = 0
    right_ptr = len(base)-1

    # 일단 mid가 사거리 내에 있는지 판별
    while True:
        mid = (left_ptr + right_ptr)//2
        if min_base <= base[mid] and base[mid] <= max_base:
            return 1
        if base[mid] < min_base:
            left_ptr = mid + 1
        else:
            right_ptr = mid - 1
        if left_ptr > right_ptr:
            break
    return 0
    


for i in range(N):
    x, y = map(int,sys.stdin.readline().split())
    # 사로 탐색 최대 거리 
    max_base = x + (L - y) 
    # 사로 탐색 최소 거리
    min_base = x - (L - y)
    count += search(x, min_base, max_base)
    # print("x:", x, "y:", y, "count:", count)

print(count)

 

 

 수가 많은 데이터를 기준으로 생각해야한다는 것을 다시 한번 또 배웠다.