파이썬) 공유기 설치 - BOJ

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

 

 

n, c = map(int, input().split())

arr = []

for i in range(n):
    arr.append(int(input()))

arr.sort()

start = 1
end = arr[-1] - arr[0]
#최대거리

answer = 0

while start <= end:
    mid = (start + end) // 2
    #거리 설정
    cnt = 1
    #첫번재 집은 무조건 설치
    last = arr[0]
    #마지막으로 설치된 집의 위치

    for i in range(1, len(arr)):
        if arr[i] >= last + mid:
            #거리가 mid만큼 떨어져잇다면
            cnt += 1
            last = arr[i]

    if cnt >= c:
        #설치한게 주어진 조건보다 작거나 같으면
        #거리를 더 줄여도 됨
        start = mid + 1
        answer = mid
    else:
        #반대라면 거리를 좀 늘려야 됨
        end = mid - 1

print(answer)

이 문제는 무엇을 mid로 둘지, 그리고 어떤 경우에 start와 end를 건드릴지 고민이 되었다.

우선 mid는 거리로 두기로 결정했따.

만약 거리가 4라면 공유기 설치는 다음과 같다

1

2

3

4

5

6

7

8

9

위에서 설치 가능한 집은 1,2,4,8,9가 되고

거리를 4만큼 떨어져 있어야한다는 조건 아래에 공유기를 설치한다면

 

1, 8이 된다.

거리가 4일때 공유기는 두 개밖에 설치하지 못한다.

공유기가 부족하다 => 더 설치해야한다 => 거리를 좀 더 좁히자

거리가 3일때 생각해보자.

설치가능한 집은

1,4,8

또는 1,4,9가 된다.

공유기 설치의 거리가 3이라면 3개가 충분히 가능하다.

그럼 마찬가지로 거리가 2일때도 그보다 큰 3이 가능했으니 당연히 거리 2또한 가능하다.

즉, 거리가 3보다 작거나 같다면 공유기 설치가 가능하다는 뜻이다.