[백준] 2110번 공유기 설치 이분 탐색

2024-05-16 내 기준 어려운 문제 풀이 정리
문제 링크 : https://www.acmicpc.net/problem/2110
집의 좌표들이 주어지면 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 문제이다.

• n과 x의 범위가 매우 큰 경우에는 (n은 20만, x는 10억) 이진 탐색 문제가 아닐까 고민해보는 것이 좋다고 한다.
• 가장 인접한 두 공유기 사이의 최대 거리를 이진 탐색으로 찾으면 𝑂(𝑛∗𝑙𝑜𝑔𝑥)O(n∗logx)만에 문제를 해결할 수 있다.

이분 탐색으로 풀 시, start와 end point를 어떻게 정의할지, 또 이를 어떻게 업데이트할지 고민했다.
 
처음에는 집의 index를 start, end point로 잡고 / 거리를 비교하며 start, end update / C값(설치할 공유기 수)을 하나씩 줄여보았다. 

import sys
input = sys.stdin.readline

N, C = map(int, input().split()) # house, router
x = [int(input()) for _ in range(N)]

def max_distance(start, end):
    global C 
    while C:
        mid = (start + end)//2
        if x[mid]-x[start] > x[end]-x[mid]:
            start = mid + 1
        else:
            end = mid - 1   
        router_installed.append(x[mid])
        C -= 1

x.sort()
router_installed = [x[0], x[-1]]
C -= 2
max_distance(1, len(x)-1)

router_installed.sort()
res = []
for a, b in zip(router_installed[1:], router_installed):
    res.append(a-b)
# print(router_installed)
# print(res)
print(min(res))

 
하지만 틀렸습니다. 나옴
이분 탐색으로 풀어보고자 조건문을 생각해낸게 mid start, end mid 거리 비교인데, 두 거리를 비교해서 
index point를 조정하는게 잘 와닿진 않았다.
다른 풀이를 보니, 가장 인접한 두 공유기 사이의 최대 거리는 최대 중간 값에 해당한다는 것을 깨달았고, 이를 조건문 식으로 사용한다고 하면 다음과 같이 정의될 수 있다.

1. start, end point를 거리 개념으로 놓고 mid 값을 기준으로 공유기를 설치해본다.
2. 설치 가능한 공유기 수와 설치할 공유기 수를 비교하여 공유기 사이 거리를 조정한다.

import sys
input = sys.stdin.readline

N, C = map(int, input().split()) # house, router
house = [int(input()) for _ in range(N)]

house.sort()
start, end = 1, house[-1]-house[0]
while start <= end:
    mid = (start+end)//2
    current = house[0]
    cnt = 1
    # 공유기 설치 몇 대 할 수 있는지 체크
    for i in range(1, N):
        if house[i] - mid >= current:
            cnt += 1
            current = house[i]
    
    # 공유기 설치 수가 목표 보다 크면 공유기 사이 거리 늘림
    if cnt >= C:
        start = mid + 1
        result = mid
    # 공유기 설치 수가 목표 보다 작으면 공유기 사이 거리 줄임
    else:
        end = mid - 1

print(result)

 
여기서 마지막 결과값으로 mid를 바로 출력하면 틀린다.
if cnt>=C일 때 result = mid 로 담아서 result를 출력해야 정답이 나왔는데,
이 부분이 이해가 잘 안가서 게시판에 질문을 남겼다.
https://www.acmicpc.net/board/view/142997 
 

References

• https://velog.io/@sbkwon16/%EB%B0%B1%EC%A4%80-2110%EB%B2%88-Python
• https://janeljs.github.io/search/bj-2110/