[ 파이썬][백준] 2110번: 공유기 설치

1. 문제

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

2110번: 공유기 설치

문제 유형: 2진 탐색

 

• 집의 좌표가 1,000,000,000이므로 이진 탐색을 이용해야 함
  • 시간 복잡도: O(NlogX)
• 공유기 사이의 거리의 최솟값과 최댓값을 계산
• 최솟값과 최댓값을 이용하여 중간값을 계산
• 중간값을 이용하여 c개만큼의 공유기를 설치할 수 있는지 확인
• 설치할 수 있으면 최솟값 = 중간값 + 1, 설치할 수 없으면 최댓값 = 중간값 - 1로 값을 바꾸어 반복하여 실행

2. 소스코드

import sys


n, c = map(int, sys.stdin.readline().split())
house = []
for _ in range(n):
    house.append(int(sys.stdin.readline()))
house.sort()

min_gap = house[1] - house[0]
max_gap = house[-1] - house[0]
result = 0

while (min_gap <= max_gap):
    gap = (min_gap + max_gap) // 2
    value = house[0]
    count = 1
    for i in range(1, len(house)):
        if house[i] >= value + gap:
            value = house[i]
            count += 1
    if count >= c:
        min_gap = gap + 1
        result = gap
    else:
        max_gap = gap - 1

print(result)