백준 2110: 공유기 설치 - 이분 탐색(파이썬)

공유기 설치 성공다국어

 

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

내 코드

import sys
n,c=map(int,sys.stdin.readline().split())

arr=[]
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort() #집들의 좌표를 오름차순 정렬.

start=1 #공유기 간격의 최소값은 1 세팅.
end=arr[-1]-arr[0] #공유기 간격의 최대값은 첫번째~마지막 거리로 세팅.

answer=0
while start<=end:
    mid=(start+end)//2 #예상 거리를 최소와 최대 사이값으로 시작.

    base=arr[0] #무조건 일단 첫번째 놈부터 시작해야함.

    cnt=1
    for i in range(1, len(arr)):
        if arr[i]-base>=mid: #기준점과 특정점과의 거리가 mid보다 크거나 같으면,
            cnt+=1 #공유기 설치 가능임.
            base=arr[i] #기준점을 방금 설치한 지점으로 업데이트.
    
    #위의 for문을 다 돌고,
    if cnt>=c: #그 개수가 c개 이상이면,
        answer=mid #이 때의 mid를 정답으로 업데이트.
        start=mid+1 #간격을 더 늘려볼만 하다.
    else: #그 개수가 c개에도 못 미치면,
        end=mid-1 #간격을 줄여서 더 많이 설치하게 해야한다.

#답 출력
print(answer)

 

풀이 및 접근)

- 문제를 봤을 때, 모든 경우의 수를 다 해보는 것 밖에 생각이 안났는데, 그렇게 하면 무조건 시간초과가 뜰 것 같았다.

- 그래서 알고리즘 분류를 확인했는데 이분 탐색이었다. 이분 탐색으로 푸는 것을 인지했는데도 어떻게 적용할지 잘 떠오르지 않았다.

- 전체적인 구조는 다음과 같다. 될 수 있는 공유기 사이의 거리는 최소 1, 최대 맨앞~맨뒤의 간격이다. 이 최소~최대의 범위를 점점 줄여나가며 조건을 만족하는 가장 큰 값을 찾아낸다.

- 코드에서 mid가 공유기 간의 간격을 뜻하고, 이를 변화시켜 나간다. 특정 mid값을 공유기 간의 간격으로 했을 때 설치할 수 있는 공유기의 수가 설치하고자 하는 공유기 수 이상이면 간격을 더 늘릴 수 있다는 뜻이고, 그 개수가 설치하고자 하는 공유기 수에 못 미치면, 간격을 줄여 공유기를 더 설치해야 된다는 뜻이다.

- 이런 알고리즘으로 mid값을 가장 최대로 얻을 수 있을 때가 정답이다. 이는 코드에서의 이분 탐색 탈출 조건과 동일하다.

 

- 이분 탐색은 항상 탈출 조건이나 이것을 문제에 어떻게 적용할지가 참 어려운 것 같다. 더 많은 이분 탐색 문제를 풀면서 감을 익혀나가야겠다.