[python] 백준 2110번 공유기 설치

백준 2110번 공유기 설치

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

문제

풀이

이 문제를 보고 일단 이분탐색이라는 걸 알아내는 것도 대단하다.
여기서의 핵심은 start, end, mid 설정에 있다.
start 는 공유기를 설치할 수 있는 최소 거리를 나타내고, end는 공유기를 설치할 수 있는 최대 거리, 즉 data[-1]-data[0]을 나타낸다.
그리고 current 를 통해 현재 위치를 설정해줘야만 하고, 현재 집과의 거리가 mid 이상인 경우, current를 i집으로 업데이트 시켜줘야 한다.
여러모로 머리가 빠지는 문제.
헤어 나올 수가 없네.

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

data.sort()  # 집의 위치를 오름차순으로 정렬

start = 1  # 가능한 최소 거리
end = data[-1] - data[0]  # 가능한 최대 거리

while start <= end: 
    count = 1  # 첫 번째 집에 공유기 설치
    mid = (start + end) // 2
    current = data[0]  # 현재 위치

    for i in range(1, n):
        if data[i] - current >= mid:  # 현재 집과의 거리가 mid 이상인 경우
            count += 1
            current = data[i]
    
    if count >= c:  # 공유기를 설치한 집의 수가 c보다 많거나 같다면
        result = mid
        start = mid + 1  # 더 큰 거리로 탐색
    else: 
        end = mid - 1  # 더 작은 거리로 탐색

print(result)

📌 주의

• 시간 초과 되면 일단 이분탐색? 투포인터? 슬라이딩 윈도우? 머릿속에서 막 던져보자. 그 중에 하나는 걸리겠지.