179. 2110(공유기 설치) - 파이썬

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
home = sorted(list(int(input()) for _ in range(N)))

start = 1  # 최소거리
end = home[-1] - home[0]  # 최대거리
result = 0

while(end - start >= 0):
    mid = (start + end) // 2
    currentHome = home[0]
    wifi = 1

    for i in range(1, len(home)):
        if home[i] >= currentHome + mid:
            wifi += 1
            currentHome = home[i]

    if wifi >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

문제요약

가지고 있는 공유기 개수 만큼 집에 설치 했을 때 두 집의 최대 거리를 구하라.

설명

집이 1 2 4 8 9 에 위치해 있다고 하자.

 

두 집 사이의 거리가 가장 작게 설치되는 거리는 1이다.

두 집 사이의 거리가 가장 크게 설치되는 거리는 9 - 1 로 8이다.

start = 1  # 최소거리
end = home[-1] - home[0]  # 최대거리
result = 0

 

 

따라서 1~8까지 후보군이며 먼저 mid 값을 8 + 1 / 2 로 4를 설정한다.

오름차순으로 정렬하였고 처음 집부터 설치를 진행한다.

공유기는 end 거리만큼 최소 한개를 설치 할 수 있기 때문에 1로 설정한다.

while(end - start >= 0):
    mid = (start + end) // 2
    currentHome = home[0]
    wifi = 1

 

 

현재 1을 기준으로 5칸 보다 크고 가장 인접한 집은 8이다.

1번에 설치를 하고 현재 집을 8로 바꾸면 12보다 거리가 큰 곳을 찾아야 하는데 9가 최대로 공유기는 총 2곳에만 설치하게 된다.

    for i in range(1, len(home)):
        if home[i] >= currentHome + mid:
            wifi += 1
            currentHome = home[i]

 

그러면 4보다 크거나 같은 위치에는 공유기 3개 설치가 불가능하다!

따라서 1~3내에서 공유기 3개를 설치하고 간격이 가장 큰 곳을 찾게 된다.

    if wifi >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

 

이 과정을 반복하며, 공유기 설치 갯수가 도현이가 원하는 만큼보다 크거나 같으면 일단 답으로 저장하며, 시작위치가 끝 위치보다 크거나 같을 때 까지 진행한다.