[그리디] Parametric Search / 폭탄 떨구기

문제링크

https://www.codetree.ai/missions/8/problems/drop-the-bomb?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 이분탐색의 대상이 되는 값 → R
  • R로 결정할 수 있는 것은 바로 주어진 범위를 덮는 폭탄의 개수를 결정한다.
  • 덮어야하는 포인트의 첫 시작은 반드시 폭탄의 범위에 들어가야 하므로 이를 폭탄의 시작점으로 생각한다.
• 폭탄의 범위에 대한 생각
  • (R ~ 폭탄 ~ R) 로 생각할수도 있지만  (폭탄 ~ 2 * R)로 생각할 수 있다. 후자가 다루기 훨씬 편하다.
• 코드 해설
  • 범위 R에 따른 필요한 폭탄의 수 세는 방법: 폭탄의 범위를 -inf로 초기화를 해놓은 상태에서 각 point들이 폭탄의 범위 들어가 있는지 확인한다. 만약 point의 처음에 설정한 폭탄의 범위보다 크면 새로운 폭탄을 하나 더 설정하여 그 범위를 커버해야한다.
  • 범위R이 커질수록 필요한 폭탄의 수는 감소한다. 우리는 폭탄을 최대 K를 설치할 수 있다.
    • 왜냐하면 K개보다 적게 설치해서 모두 커버된다면 R이 무진장 크다는 것이고 나머지 폭탄은 아무곳에나 설치해도 전부 커버가 되기 때문이다.
    • 그런데 K개 보다 많이 설치하게 되면 폭탄이 터지는 범위 R이 조금 부족하다는 의미가 되므로 R을 키워야한다.
    • 따라서 폭탄의 최대 K개까지 설치하도록 해야한다.
    • R 5(F) 4(F)  || 3(T) 2(T) 1(T) → 이 경우 최대 3개까지 설치할 수 있는 것을 의미하는데 오른쪽이 True이다. 따라서 정답 영역은 오른쪽에 존재한다.

2. 코드(Python)

n, k = map(int, input().split())
points = [int(input()) for _ in range(n)]
points.sort()
inf = int(1e9)
# 좌표위치...10^9..매우 큼! -> 이분탐색
# 이분탐색의 대상: 'R'
# 폭탄의 위치는...?
# 현재 정답 기준 R이 5보다 작으면 F / 5보다 크거나 같으면 T
# (R 폭탄 R) 로 생가하지말고 2R 막대기라고 생각하자!

def get_count(r):
    max_bomb_range = -inf
    
    bomb_cnt = 0
    for point in points:
        if point > max_bomb_range:
            max_bomb_range = point + 2 * r
            bomb_cnt += 1
    return bomb_cnt

# k = 3
# 1 2   3 4 5 .. r
# 5 4 | 2 1 .. bomb_cnt(r)
# F F | T T 
# 폭탄이 최소 k개는 되야함
# k개 보다 폭탄이 적으면 나머지 폭탄은 아무데나 뿌려도 된다.
def binary_search(target):
    l, r = 0, inf
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if get_count(mid) <= target:
            ans = mid
            r = mid - 1
        else:
            l = mid + 1

    return ans

print(binary_search(k))