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

2110 공유기 설치

1. 문제유형

• Binary Search

2. 자료구조

• cnt (int): 공유기 개수
• left (int): 최소 거리 == 1
• right (int): 최대 거리 == (마지막 집 좌표 - 첫 번째 집 좌표)
• mid (int): 공유기 간 거리 == (left + right) // 2
• wifi (int): 공유기가 설치된 집 좌표

3. 해결과정

• 집 좌표 최대 크기가 10억이므로, 순차탐색이 아닌 이분탐색을 떠올려볼 것
• 공유기 간 최대거리를 찾는 것이 목적이므로 이분탐색 활용할 것

1. left <= right일 동안 아래 과정을 반복하며 중간값이 최대가 되는 값은 탐색한다.
2. 중간값 mid = (left+right)//2로, 최초 공유기 개수는 1, 최초 공유기 위치는 house[0]으로 설정한다.
3. 반복문을 돌며 2번째 집부터 마지막 집까지 아래 조건을 체크한다.
4. i번째 집 좌표가 이전 공유기 위치로부터 + 최대거리(중간값 mid)을 넘어서면 새로운 공유기를 설치하고, 공유기 개수를 증가시킨다.
5. 반복문 종료 후, 공유기 개수가 c보다 작다면 최대거리가 긴 것이므로 right = mid - 1
6. 공유기 개수가 c보다 크다면 최대거리가 짧은 것이므로 answer에 최대거리 저장 후 left = mid + 1
7. answer를 출력한다.

import sys

n,c = map(int, input().split())
house = list(int(sys.stdin.readline()) for _ in range(n))
house.sort()

left = 1
right = house[-1]-house[0]
answer = 0

while left <= right:
    mid = (left+right)//2
    cnt = 1
    wifi = house[0]

    for i in range(1, n):
        if house[i] >= wifi + mid:
            cnt += 1
            wifi = house[i]

    if cnt < c:
        right = mid - 1
    else:
        left = mid + 1
        answer = mid
print(answer)