[이분탐색] 백준 2110번 '공유기 설치' (Python)

<문제 링크>

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

2110번: 공유기 설치

---

<문제 풀이>

1. 처음 최소 거리는 항상 1, 최대 거리는 max-min

2. mid 거리만큼 차례대로 공유기를 설치함. (집이 1,4,8,9이고, mid가 4일 때, 1,8에 공유기 설치 가능) 

3. 2개밖에 설치 못하므로 거리-1, 그 반대면 +1

 

<코드>

#이취코 답
n,c = list(map(int,input().split()))

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

start = 1
end = array[-1]-array[0]
result = 0

while start<=end:
	mid = (start+end)//2
    value = array[0]
    count = 1
    for i in range(1,n):
    	if array[i] >= value+mid:
        	value = array[i]
            count += 1
    if count >= c:
    	start = mid+1
        result = mid
    else:
    	end = mid-1
print(result)

 

<고쳐야 할 점>

• 최적의 결과 저장하는 법 기억!!
• 문제 자체 이해하기,,,
• 복습 알고리즘