[Baekjoon] 2110번 : 공유기 설치 (Python, 이분 탐색)

[Baekjoon] 2110번 : 공유기 설치 (Python, 이분 탐색)

 

목차

 

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

2110번: 공유기 설치

Python

 

방법 1 - 메모리 40132KB / 시간 7740ms / 코드 길이 384B

 

사실 본 문제에 대하여 이분탐색이라는 것을 알고 시작했다.

그러나 좌표에 대한 것을 토대로 이분 탐색을 진행하려던 것이 틀린 길로 인도하였다.

실제 본 문제를 풀기 위해서는 집과 집 간의 공유기 거리(Gap)를 기반으로 이분 탐색을 진행해야 한다.

때문에 2개의 공유기간의 간격 거리 즉, start: 1부터 end: 최대 거리(집 좌표의 마지막 값 - 처음 값)를 기반으로 이분 탐색을 진행한다.

 

이와 같은 start와 end 값 즉, 공유기 간의 거리를 기반으로 이분 탐색을 진행할 때 공유기가 몇 개 설치되는지를 위한 for문을 작성한다.

이후 설치가능한 공유기의 개수와 설치해야 하는 공유기 개수를 비교한 후 이에 따른 전형적인 이분 탐색을 진행한다.

 

n,c = map(int, input().split())
l = sorted([int(input()) for _ in range(n)])
start = 1
end = l[n - 1] - l[0]

while start <= end:
    cnt = 1
    mid = (start + end) // 2
    current = l[0]
    for x in l:
        if current + mid <= x:
            cnt += 1
            current = x
    if cnt >= c:
        start = mid + 1
        ans = mid
    else:
        end = mid - 1

print(ans)