백준 공유기 설치 파이썬

 

2110번: 공유기 설치

공유기 사이의 최대 거리를 찾는 문제로, 입력이 20만인 것을 보면 시간 복잡도는 nlogn이하로 만들어야한다.

이진 탐색으로 문제를 해결을 해보자.

최소 거리를 s, 최대 거리를 e라고 했을 때 중간값을 탐색하면서 조건(공유기를 해당 값 거리 만큼씩 설치할 수 있는가)에 맞는지 체크하면 문제를 해결할 수 있다.

코드

n, c = map(int,input().split())
h = []
for _ in range(n):
    h.append(int(input()))

h.sort()
s = 1
e = h[-1] - h[0] # 설치 가능한 최대 거리는 제일 큰값 - 제일 작은값
result = 0
while s <= e: # 이분탐색
    mid = (s+e)//2
    cnt = 1
    temp = h[0]
    for i in range(1,n): # 현재 중간값으로 공유기를 설치 가능한지 체크
        if temp + mid <= h[i]:
            temp = h[i]
            cnt += 1
    if cnt >= c: # c개 이상의 공유기를 설치 할 수 있다면 중간값 범위를 더 증가시킨다.
        s = mid + 1
        result = mid
    else: # c개 미만으로 공유기 설치가 가능하다면 중간값 범위를 줄인다.
        e = mid -1
print(result)

이분탐색은 입력값이 크고, 탐색 문제일 때 효율성이 좋은 알고리즘이다.

탐색하려는 값을 mid 값으로 정하고 범위 내에서 이분 탐색을 하면 좀 더 풀이 방법을 빠르게 떠올릴 수 있다고 생각한다.