[ BOJ 2110 ] 공유기 설치(Python)

문제

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

공유기는 집이 위치한 좌표에 설치할 수 있다.
n개의 집에 c개의 공유기를 둘 때, 가장 효율적으로 놓을 수 있는 위치를 찾으면 된다.
어려웠던 문제 , , , 🤯🔨

문제 풀이 (🔗 참고)

1. 집 위치 입력 받고 정렬

for _ in range(n):
    position.append(int(input()))
position.sort()

2. 이분 탐색 할 범위 선언

l, r = 0, position[-1] - position[0]

첫번째 집을 포함해서 공유기를 설치할 것이기 때문에 시작 범위는 0.
l = 0
첫번째 집에서 가장 먼 집까지의 거리를 끝 범위로 정해준다.
r = position[-1] - position[0]

mid 는 공유기 사이의 거리를 의미한다.

3. 공유기 개수를 카운트 해주는 함수 정의

def counter(distance):
    cnt = 1
    curr_p = position[0]
    
    for i in range(1, n):
        # (현재 위치 + 거리) 가 다음 위치까지 닿지 않으면 공유기 개수 + 1
        if curr_p + distance <= position[i]:
            cnt += 1
            curr_p = position[i]
    return cnt

매개변수로 받은 mid (= distance) 와 현재 위치 를 더한 값이 다음 위치 거리 보다 짧으면 현재 공유기 사이 거리로는 닿지 않는다는 뜻이다.
따라서 공유기 개수를 +1 해준다.

그리고 현재 위치를 다음 공유기 위치로 바꿔준다.
공유기 개수를 리턴한다.

4. 함수 리턴값을 입력받은 공유기 개수 c와 비교

# 공유기 개수가 c와 같거나 많으므로 거리를 늘려준다.
    if counter(mid) >= c:
        result = max(result, mid)
        l = mid + 1
# 공유기 개수가 c보다 적으므로 거리를 좁혀준다.
    else:
        r = mid - 1

l이 증가 = mid값 증가 = 공유기 사이 거리 증가
r이 감소 = mid값 감소 = 공유기 사이 거리 감소

코드

import sys
input = sys.stdin.readline

# c개의 공유기를 n개의 집에 설치, 가장 인접한 두 공유기 사이의 최대 거리 구하기
n, c = map(int,input().rsplit())
position = []
result = 0

for _ in range(n):
    position.append(int(input()))
position.sort()

def counter(distance):
    cnt = 1
    curr_p = position[0]
    for i in range(1, n):
        # (현재 위치 + 거리) 가 다음 위치 거리보다 짧으면 공유기 개수 + 1
        if curr_p + distance <= position[i]:
            cnt += 1
            curr_p = position[i]
    return cnt

# r : 가장 먼 집 사이의 거리
l, r = 0, position[-1] - position[0]

while l <= r:
    mid = (l + r) // 2
    #print(">>c:{3}, mid:{0}, l:{1}, r:{2}".format(mid,l,r,c))

    # 공유기 개수가 c와 같거나 많으므로 거리를 늘려준다.
    if counter(mid) >= c:
        result = max(result, mid)
        l = mid + 1
    # 공유기 개수가 c보다 적으므로 거리를 좁혀준다.
    else:
        r = mid - 1

print(result)