백준 2110. 공유기 설치

WooHyeong·2022년 12월 19일
0

Algorithm

목록 보기
4/41

Binary Search 기출 문제 29. 공유기 설치
집 N개가 수직선 위에 있다. 와이파이를 즐기기 위해 집에 공유기 C개를 설치하려고 한다.
한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를
가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

Example1
input

5 3
1
2
8
4
9

output

3

풀이

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

#1부터 가장 마지막 집의 좌표의 값으로 start, end 초기화
start = 1
end = array[-1]
result = 0

# 이진탐색 실행
while start <= end:
    mid = (start + end)//2
    value = array[0] # 첫번째 집의 좌표
    count = 1 # 공유기 수
	
    
    for i in range(1, n):
    # 현재 집에 mid(거리)를 더한 값이 다음 집보다
    # 작으면 공유기를 더 설치할 수 있으므로 count를 증가시켜준다.
        if array[i] >= value + mid:
            count += 1
            value = array[i]
            
	# C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소한다.
    if count < c:
        end = mid -1
        
    # C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가한다.
    else:
        start = mid + 1
        result = mid

print(result)





profile
화이링~!

0개의 댓글