[백준/Python] 공유기 설치

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

2110번: 공유기 설치

N, C = map(int, input().split())
house = [int(input()) for _ in range(N)]
house.sort() # 오름차순 정렬
low, high = 1, house[-1] - house[0]

while low <= high:
    mid = (low + high) // 2
    cur = house[0] # 공유기를 설치한 마지막 위치
    count = 1 # 설치한 공유기 개수

    # 앞 집부터 공유기 설치
    for i in range(1, N):
        if house[i] >= cur + mid:
            cur = house[i]
            count += 1

    if count >= C:
        low = mid + 1
    else:
        high = mid - 1

print(high)

1. 필요한 정보를 입력받은 뒤 house를 오름차순 정렬한다.

2. 이분탐색을 한다.

     2-1. mid를 구한 뒤 cur, count를 초기화한다.

     2-2. 앞 집부터 공유기를 설치한다. 집의 좌표(house[i])가 cur + mid보다 크거나 같다면 공유기를 설치한다.

     2-3. count > = C 인 경우 거리를 더 넓게 공유기를 설치할 수 있다는 것이므로 low = mid + 1

     2-4. count < C 인 경우 거리를 줄여야하므로 high = mid - 1

3. 결과를 출력한다.