[백준 2110] 공유기 설치 - python (solved.ac - 골드 5)

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

2110번: 공유기 설치

풀이

문제를 보았을때 알수있는 힌트

정해져있는 공유기 개수를 최대한 멀리 떨어트려서 설치하는 문제이다. 처음과 끝의 가운데에 설치하면 되지 않을까? 라는 생각을 가지고 풀면 될듯 싶었다.

여기서 찾아보니 이진 탐색을 통해서 풀면 빠르게 풀린다는 것을 알고 이해하는데 시간이 걸렸다.

무조건 처음 1번 집에 공유기를 설치 했다는 가정하에 시작을 해보자

1번 집에 설치 후 끝인 9번 집의 거리인 8의 가운데 4의 거리 만큼 떨어져있는 곳에 설치하면 최대 길이일 것이다.

1번 집 다음으로 4만큼 거리이기에 5번 집 이상이어야한다. 고로 처음 나오는 8번집이 된다. 이후 8번 집에서 4만큼 떨어진 12번 집 이상을 찾아야한다. 하지만 최대 집인 9이기에 더이상 설치 할 집이 없다. 총 4의 길이로 설치를 한다면 1,8번집 2개만 설치한다.

이러면 우리가 생각했던 3개의 공유기 설치가 아니다. 다시 말해 4의 길이보다는 작아야한다는 이야기가 된다. 이때 최대 길이 였던 8(end)을 4(min)로 변경한다.

먼저 1번 집에서 설치하고 4의 거리에 가운데에 설치를 시도한다. 가운데는 (4+1)//2 = 2가 된다.

1번집 다음으로 2만큼 떨어진곳 으로는 4가 나온다. 4다음으로 2만큼 떨어진곳으로는 8이나온다. 이렇게 총 3번이 나오고 우리가 원하던 3개와 맞게 되었다.

이런식으로 길이를 반씩 줄이며 최대의 길이를 구하는 문제이다.

import sys

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

array = []
for i in range(n):
    array.append(int(input()))

array.sort()

def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]
        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2110.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리