BOJ 2110: 공유기 설치 [Python 3]

이번 문제는 공유기 설치라는 문제이다.

 

이 문제 또한 집의 개수가 매우 많을 수 있고, 좌표의 범위도 매우 넓다.

그렇기에 이중 for 문을 써서 풀 수도 있지만, 2초라는 시간 제한에 걸려서 시간 초과가 뜰 것이다.

---

알고리즘 해설

이분 탐색을 통해 풀었다.

---

코드

n,c=map(int,input().split())
data=[int(input()) for _ in range(n)]
data.sort()
l,r=0,data[-1]-data[0]
res=0
while l<=r:
    mid= (l+r)//2
    curr=0
    answer=1
    for i in range(1,len(data)):
        if data[i]-data[curr]>=mid:
            answer+=1 
            curr=i
    if answer<c:
        r=mid-1
    else:
        res=mid
        l=mid+1

print(res)

최소와 최대의 범위를 0부터 공유기끼리 제일 먼 길이로 떨어진 공유기들의 길이로 설정한다.

그리고 이분 탐색을 통해서 해결한다.

 

문제의 포인트는, 만약 만족하는 결과가 나와서 중간에 break하면 안 된다.

문제의 조건을 만족하는 최대 길이가 더 있을 수도 있기 때문이다. (위 그림에서도 주홍색이 정답이 아니라, 연두색이 정답이다!)

 

이분 탐색은 정말 유용하다.