[백준2110/골드4] 공유기 설치 - Python

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

 

처음엔 웅덩이 보수하기 문제처럼 그리디로 풀어야하는줄 알고 도전했는데 못풀었다!

어제부터 고민했는데 답이 안나와서 몰래 알고리즘 유형 열어봤다. 이분탐색 문제였다.

 

1. 거리 이분탐색으로 최소거리 설정하면서 최적의 거리 구하기

2. 집 하나씩 돌아다니면서 최소거리보다 더 넓게 공유기 설치할 수 있으면 설치하고 공유기 설치 수 += 1 (last 값 그 위치로 갱신)

3. 공유기 설치 수가 C보다 크면 가능 -> left = mid + 1로 갱신해서 더 넓은 거리로 다시 구하기

4. 공유기 설치 수가 C보다 작으면 불가능 -> right = mid - 1로 갱신해서 더 좁은 거리로 다시 구하기

 

 

# 성공 코드

N, C = map(int, input().split()) # 집, 공유기 수
# 가장 인접한 두 공유기 사이의 거리 가장 크기
# C개의 공유기를 채울동안 반복
# left house[0], right house[N-1]로 거리 설정 후 이분탐색하며 거리가 최대인 집 찾아서 설치

house = [int(input()) for _ in range(N)]
house.sort()

left = 1
right = house[N-1]
result = 0

while left <= right:

    mid = (left + right) // 2
    last = house[0] # 마지막 공유기 설치한 집의 위치
    count = 1

    # 집 수색하면서 거리가 mid 이상일 때만 그 집에 설치 (처음 집엔 무조건 설치하므로 1부터 수색)
    for i in range(1, N):
        if house[i] - last >= mid: # 거리가 최솟값보다 크면 설치
            last = house[i]
            count += 1

    # 공유기 충분하면 결과 갱신, 거리 늘림
    if count >= C:
        left = mid + 1
        result = mid

    # 공유기 모자라면 거리 좁힘
    else:
        right = mid - 1

print(result)