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

문제 출처:

www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제 풀이 :

• 앞서 본 이분탐색과 같은 문제이다.
• 이런 문제류에서 바뀌는 부분은 찾는 특정값을 비교할때 사용되는 결과값을 구하는 부분인데 여기서는 아마 gap을 구하는 부분만 신경 써주면 될 것이다.
  • 보통 for문으로 구하니까 복잡하지 않은 이분탐색 문제에선 while문 안에 있는 for문을 신경써서 보면 문제가 쉽게 이해가 된다.

n, c = map(int, input().split())

house = []
for _ in range(n):
    x = int(input())
    house.append(x)

house.sort()

start = 1
end = house[-1] - house[0]

result = 0

while (start <= end):
    mid = (start + end) // 2
    old = house[0]
    count = 1

    for i in range(1, len(house)):
        if house[i] >= old + mid: 
            count += 1
            old = house[i]

    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)