[백준] 공유기 설치

2110번: 공유기 설치

먼저 이문제가 이분 탐색인 이유에 대해 생각해보자

우리의 조건은 거리가 얼마나 최대한 멀게끔 하는것이다.

알아봐야 할 부분은 중요한 것은 집들이 수직선상에 위치하고 있다는 것을 생각해야 한다는 점이다.

풀이

1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬.

2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 )

3. 앞 집부터 공유기 설치

4. 설치할 수 있는 공유기 개수가 c개를 넘어가면 더 넓게 설치할 수 있다는 이야기 이므로 설치거리를 mid + 1로 설정하여 다시 앞집부터 설치. (그래도 일단 설치가 가능하니 정답에 넣을 수 있음)

5. c개를 넘어가지 않는다면 더 좁게 설치해야 한다는 이야기 이므로 mid - 1로 설정.

import sys

input = sys.stdin.readline
N,C = map(int, input().split())
arr = []
for i in range(N):
    arr.append(int(input()))

arr.sort()
start = 1
end = arr[-1]
result = -1
while start < end:
    mid = (end - start)//2
    cur = arr[0]
    count = 1

    for i in range(1,len(arr)):
        if arr[i] >= cur + mid:
            cur = arr[i]
            count += 1

        if count >= C:
            start = mid + 1
            result = mid
        else:
            end = mid -1

print(result)

개인적으로 이해가 안되는 풀이 (내가 푼 풀이)

import sys

input = sys.stdin.readline
N,C = map(int ,input().split())
arr = [int(input()) for _ in range(N)]

arr.sort()
l = 1
r = arr[-1] - arr[0]

result = 0
while l <= r:
    mid = (r + l)//2
    pre = arr[0]
    count = 1
    for i in range(1, len(arr)):
        if arr[i] >= pre + mid:
            count +=1
            pre = arr[i]

    if count >= C:
        result = count
        l = mid + 1
    else: r = mid -1

print(result)