[백준 #2110번 / Python] 공유기 설치

. 문제)

https://www.acmicpc.net/problem/211
수직선 상에 있는 N개의 집 좌표와 설치할 공유기 개수 C가 주어진다.
이후 가장 인접한 두 공유기 사이의 거리를 최대로 하여 설치하려 한다.
이를 만족하게 설치했을 때 가장 인접한 두 공유기 사이의 거리를 출력하시오.

Input)                            Output)
5 3                               3   
1
2
8
4
9

. 접근)

처음 이 문제를 보고 든 생각은, 양 끝 지점에 무조건 공유기를 설치 후 가장 긴 구간의 중간 지점마다 공유기 설치를 하면 되는 거 아닌가? 였다.
그러나 모든 지점에 집이 존재하는 것이 아니므로 정확히 2등분이 될 수 없고, 매 경우마다 N개의 집 사이 거리를 계산해줘야 하기에 시간초과가 난다.
따라서 이 문제는 주어진 정보를 통해 적절히 이분탐색을 해야 풀 수 있고 실제로 어떻게 이분탐색을 할지 고민하는 데에 시간을 많이 썼다.
최종적으로 선택한 접근 방법은 이렇다.

1. 집의 좌표를 담고 있는 house 배열을 만든다.
2. 공유기 사이 거리를 최대로 만들어야 하므로, 가장 첫 번째 집에는 무조건 공유기를 설치한다.
3. 초기 양 끝 점의 매개변수를 최소 거리와 최대 거리로 잡고 중간 값 mid를 구한다.
4. for문으로 house 배열을 이동하면서 첫 집으로부터 거리가 mid보다 같거나 크면 공유기를 설치하고 cur 변수를 갱신한다. (최근에 공유기 설치한 집)
5. 만약 설치한 공유기 개수가 C보다 작다면, 공유기 사이 거리가 긴 것이므로 end=mid-1 로 바꾼다.
6. 만약 설치한 공유기 개수가 C보다 크거나 같다면, 공유기 사이 거리가 짧은 것이므로 start=mid+1로 바꾼 뒤 다시 이분탐색을 시행한다.

. 풀이)

• 초기 매개변수 start와 end를 각각 0, house[-1]-house[0]으로 잡는다. (최소 거리 / 최대 거리)
• 최근 공유기를 설치한 집을 담는 변수 cur=house[0], 공유기를 설치한 개수를 담는 변수 cnt=1 를 선언한다.
• 2번째 집부터 N번째 집까지 방문하면서 위에서 설명한 방법으로 공유기를 설치한다.
• 이분 탐색을 끝낸 cnt 값을 결과로 반환한다.

 

. 코드)

import sys
input=sys.stdin.readline

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

def binary_search(target,start,end):
    res=1
    while start<=end:
        mid=(start+end)//2
        cnt=1
        cur=house[0]
        for i in range(1,n):
            if house[i]-cur>=mid:
                cnt+=1
                cur=house[i]
        if cnt>=target:
            start=mid+1
            res=mid
        else:
            end=mid-1
    return res
print(binary_search(c,0,house[-1]-house[0]))

. 주의할 점)

if cnt>=target 문에서 주의할 점이 한 가지 있다.
바로 cnt와 target이 같으면 바로 리턴해도 되는 게 아닌가?라는 생각 때문이다.
그러나 아래와 같은 반례를 보자.

house=[1,2,3,4,10], C=3 인 경우다.

이 경우 mid가 2로 설정된 경우 1,3,10 에 위치한 곳에 공유기를 설치하면 주어진 조건을 만족하는 걸 볼 수 있다.
그러나 1,4,10 에 공유기를 설치하면 조건을 만족하면서 동시에 거리를 더 늘릴 수 있다.
따라서 이런 실수를 막기 위해 cnt와 target이 같더라도 한 번 더 이분탐색을 수행하는 것이다.