백준 2110, 이진탐색

 

 

집 위치 : [1, 2, 4, 8, 9] 

공유기 개수 : 3

 

목표 : 공유기가 설치된 집들 간의 거리의 최소값을 최대로 만들자. 

 

최소 거리 : 2 -1 = 1

최대 거리 : 9 -1 = 8

 

따라서, 최대가 될 수 있는 최소 거리의 후보는 아래와 같다. 

1, 2, 3, 4, 5, 6, 7, 8

# 거리 중, "최소"거리가 "최대"여야 함. 
def can_place_routers(houses, C, distance):
    count = 1
    # 첫번째 집에 공유기 설치
    last_router = houses[0]
    # last_router은 가장 마지막에 공유기를 설치한 집.
    
    # 나머지 집에 공유기 설치
    for i in range(1, len(houses)):
    	# i번째 집 - 가장 마지막에 공유기를 설치한 집의 거리가 mid보다 크면? 우리가 찾던 상황
        if houses[i] - last_router >= distance:
        	# 여기에 설치
            count += 1
            # 가장 마지막에 공유기를 설치한 집을 i번째 집으로 변경
            last_router = houses[i]
        if count >= C: # 이렇게 3개를 전부 설치할 수 있다면, 가능한 것
            return True
    
    return False

def find_max_min_distance(houses, C):
    # 1 2 8 4 9 -> 1 2 4 8 9
    houses.sort()
    
    # 최소 거리는 1
    start = 1
    # 최대 거리는 가장 멀리 떨어진 두 집 사이 거리. [-1]을 통해 가장 끝 요소를 구할 수 있음=8
    end = houses[-1] - houses[0]
    # result 초기화
    result = 0
    
    # 최소 거리에서 시작한 변수가 최대 거리에서 시작한 변수보다 커질때까지 반복함
    while start <= end:
    	
        # 중간값을 구함 1 + 8 = 9, 중간 4
        mid = (start + end) // 2
        
        # [1 2 4 8 9], 3, 4. 4는 될까?
        if can_place_routers(houses, C, mid):
            result = mid
            start = mid + 1  # 4도 되네, 그러면 더 큰 중간값을 만들기. 2 + 8, 중간 5
        else:
            end = mid - 1  # 4는 안되네, 그러면 더 작은 중간값을 만들기. -1 + 8, 중간 3
    
    return result

# 입력 처리
N, C = map(int, input().split())  # N: 집의 개수, C: 공유기의 개수
houses = [int(input()) for _ in range(N)]

# 결과 출력
print(find_max_min_distance(houses, C))