[백준] 공유기 설치 (2110번) - Python

✅문제 - 공유기 설치 (2110번) 

---

 

✅필요 알고리즘 개념 - 이분탐색

---

◼ 이 문제의 키 포인트는 공유기 사이의 거리를 이분 탐색으로 찾는 것이다.

◼ 공유기 간의 가장 가까운 거리는 1 가장 먼 거리는 마지막 좌표 - 첫 좌표가 된다. 이 거리 사이에서 이분탐색을 통하여서 최대 거리를 구하면 된다.

 

✅코드

---

import sys
import bisect

input = sys.stdin.readline

n,c = map(int,input().rstrip().split())
house_distance = []

for _ in range(n):
    house_distance.append(int(input().rstrip()))
# 이분 탐색은 정렬된 list에서 사용하는 것이므로 정렬한다.
house_distance.sort()

# 공유기 간의 거리를 min과 max로 하여 우리가 원하는 최대 거리를 구한다.
min_distance = 1
max_distance = house_distance[-1]
# 그 전 값과 비교하기 위해 초기 값을 tmp에 저장한다.
tmp = house_distance[0]

# 이분 탐색 시작
while min_distance <= max_distance:

    # 공유기 간의 거리가 가장 멀기 위해서는 처음 집에 무조건 공유기를 설치한다.
    tmp = house_distance[0]
    count = 1
    # 이분 탐색을 위한 mid / 이 값은 공유기 간의 거리를 의미한다.
    mid = (min_distance + max_distance)//2
    for i in range(1,n):
        # 집과 집 사이의 거리가 mid 이상인 경우에 공유기를 설치하고 count += 1을 한다.
        if house_distance[i] >= tmp + mid:
            # 비교를 위해 tmp에 그 전에 방문한 집의 좌표 저장
            tmp = house_distance[i]
            count += 1

    # count >= c 인 경우 거리를 더 증가 시켜도 된다는 뜻
    if count >= c:
        # 그러므로 min_dis의 거리를 mid + 1로 증가시킨다.
        min_distance = mid + 1
    else:
        # c개의 공유기를 설치하지 못했으므로 거리를 줄인다.
        max_distance = mid - 1

print(max_distance)