백준 2110: 공유기 설치 (Python)

 

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

2110번: 공유기 설치

 

첫 제출은 시간 초과가 떴다..

입력받는 부분만 sys.stdin.readline()으로 바꿔주니까 통과함

 

import sys

n, c = map(int, sys.stdin.readline().split())
house = [int(sys.stdin.readline()) for _ in range(n)]
house.sort()

start = 1
end = house[-1] - house[0]

while start <= end:
    mid = (start + end) // 2
    count = 1
    current = house[0]

    for i in house:
        if current + mid <= i:
            count += 1
            current = i

    if count < c:
        end = mid - 1
    else:
        start = mid + 1

print(end)

 

이걸 어떻게 이진탐색으로 풀지?!하고 감이 안 잡혔었는데

start = 1, end = 배열 내 최대 거리 로 놓고 값을 조절해가면서

mid값을 공유기 설치의 거리(?)로 이용하면 된다.

 

앞에서부터 공유기를 설치하는데 거리가 mid 이상인 것만 공유기를 설치해주고

공유기 설치한 개수가 C보다 작으면 공유기를 더 설치할 수 있으므로 거리를 좁혀주면 된다. (end 범위 줄이기)

반대로 C보다 크거나 같으면 거리 넓히기 (start 범위 늘리기)