[Python] 백준 2110번 : 공유기 설치

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

2110번: 공유기 설치

---

💡 문제 풀이

이분 탐색 문제이다.

 

입력받은 집의 위치를 정렬해서 이분 탐색을 진행한다.

이분 탐색 시 mid는 공유기 사이의 거리를 의미한다.

따라서 최소거리는 1, 최대 거리는 마지막 집과 처음 집의 간격이다.

지금 설치하려는 위치가 확인하는 간격(mid)을 벗어나는지 확인하면서 설치한 공유기 개수를 세어준다.

설치한 개수가 c보다 크다면 간격을 더 늘려도 된다는 소리이고, 반대로 작다면 간격을 줄여야 한다.

✔️ 느낀 점

크게 어렵지 않은 문제이다. 다만 이번에 sort()와 sorted()의 차이를 놓쳐서 계속 틀렸다고 나왔다.. ㅂㄷㅂㄷ

💻 코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
home = [int(input()) for _ in range(n)]
home.sort()

left, right = 1, home[-1] - home[0]

while left <= right:
    mid = (left + right) // 2
    router = home[0]
    cnt = 1
    
    for i in range(1, n):
        if home[i] >= router + mid:
            router = home[i]
            cnt += 1
            
    if cnt < c: right = mid - 1
    else: 
        left = mid + 1
        ans = mid
    
print(ans)