[BAEKJOON] 8983_사냥꾼_Python

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

8983번: 사냥꾼

문제

 

 

문제 해설

(1) 총을 쏘는 사대, 동물의 위치 좌표가 총의 사정거리와 함께 주어진다.
(2) 모든 동물 중, 잡을 수 있는 동물의 최댓수를 출력하면 된다.

 

 

문제 풀이

아주 다양한 아이디어가 떠올라서 시도했으나 자꾸 60점에서 막혔었다 ㅠㅠ 알고보니 이진탐색을 적용해야 효과적인 부분이었고, 풀고나니 이진탐색 적용할 부분도 사실 어렵지 않게 떠올릴 수 있는 유형이었는데 왜 그걸 생각을 못했을까.
문제풀이 아이디어는 거의 곧바로 떠올랐었다.

1. 우선, 60점 부분점수를 맡을 때의 풀이 아이디어는 총을 쏘는 사대를 기준으로 완전탐색을 진행하는 것이었다.

for x_shot in shot_spot:
    for k in list(animal_spot.keys()):
        if animal_spot[k] != 1:
            continue
        x_anim, y = k
        if abs(x_anim - x_shot) + y <= L:
            answer += 1
            del (animal_spot[k])

총을 쏘는 사대를 기준으로 모든 동물의 위치를 탐색해서, 현재 사대에서 쏠 수 있는 거리인지 dictionary를 이용해 체크 후, 잡을 수 있다면 해당 dictionary에서 삭제하는 형식으로 진행했다. 풀면서도 마지막 sub task는 통과 못하겠다 생각했고, 결과도 그래서 다른 아이디어를 떠올렸다.

2. 그래서 사대가 아닌, 사냥감을 기준으로 탐색하고자 하였다.

for spot in animal_spot:
    x_anim, y = spot
    if y > L:
        continue
    max_range = max(x_anim - (L - y), x_anim + (L - y))
    min_range = min(x_anim - (L - y), x_anim + (L - y))
    for p in range(min_range, max_range + 1):
        if p in shot_spot:
            answer += 1
            break

사냥감에 접근 가능한 범위 (x_min, x_max)는 간단히 구할 수 있고, 해당 범위에 사대가 있는지 체크하면 된다. 직관적으로 탐색할 범위가 사대의 개수보다 줄어들지 않을까?까지만 생각했는데, 오히려 41점을 맞아서 다른 아이디어가 있는지 생각에 빠졌었다. 그냥 여기서 저 접근가능한 범위를 전체탐색이 아닌, 이분탐색으로 찾으면 될 것을 한참을 헤맨 것이다.

3. 그래서 다시 돌아와서 사냥감 기준 탐색에 이분탐색을 적용하였고, 아래와 같이 풀 수 있게 되었다. 추가로 y값이 L보다 크다면 애초에 탐색할 필요도 없기에(어떤 사대에서도 접근 불가능) input 받을 때 걸러주는 코드도 추가하였다.

 

 

* 코드

from sys import stdin
import heapq

M, N, L = map(int, stdin.readline().rstrip().split())
shot_spot = sorted(list(map(int, stdin.readline().rstrip().split())))
animal_spot = []
answer = 0

for i in range(N):
    x, y = map(int, stdin.readline().rstrip().split())
    if y > L:
        continue
    heapq.heappush(animal_spot, (y, (x, y)))

while len(animal_spot) > 0:
    x_anim, y = heapq.heappop(animal_spot)[1]
    max_range = max(x_anim - (L - y), x_anim + (L - y))
    min_range = min(x_anim - (L - y), x_anim + (L - y))
    start = 0
    end = len(shot_spot) - 1

    while start <= end:
        target = (start + end) // 2
        if shot_spot[target] >= min_range and shot_spot[target] <= max_range:
            answer += 1
            break

        if shot_spot[target] > max_range:
            end = target - 1
        else:
            start = target + 1


print(answer)