https://www.acmicpc.net/problem/1477
시간 2초, 메모리 128MB

input :

• N M L (N, M <= 100)(100 <= L <= 1000)
• 휴게소의 위치

output :

• 첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력

조건 :

• 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

---

무언가 휴게소 간의 간격을 이분 탐색하여 정답을 찾아야 할 것 같은데 이 휴게소들 사이에만 새로운 휴게소를 넣는 것이 아닌 시작, 끝 사이에도 넣어야 하는 것을 어떻게 해야 하나 싶었는데

아주 간단한 방식이 있다.
0, l을 휴게소 배열에 추가해 버리는 거다.

그래놓고 그 사이에 새로운 휴게소들을 추가하면 된다.
그러고 해야하는 것은 그 사이의 간격을 통해 새로운 휴게소를 찾는다고 해도 원래의 휴게소와 겹치는 경우가 간혹 생길 수 있다. 중간 간격이 동일한 경우에는 나머지가 없기 때문에 이미 존재하는 휴게소에 새로운 휴게소를 넣는다고 생각하는 경우가 발생할 수 있다.

간격

그래서 간격을 구해서 -1 을 하는 경우 이를 제외하는 방식을 얻을 수 있다.

얻은 새로운 휴게소의 개수가 m보다 작은 경우에는 간격이 여전히 크기 때문에 right를 줄이고 큰 경우에는 left를 크게 한다.
그리고 정답의 경우에는 이 간격을 최소로 만드려고 하는 것이기 때문에 right를 줄이게 만든다.

2022.01.04

추가된 데이터의 경우를 판단해야함.
0으로 나누는 경우를 대비해 예외처리가 필요.

import sys

n, m, l = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
data.append(0)
data.append(l)

data.sort()
left, right = 0, l
while left <= right:
    mid = (left + right) // 2
    cnt = 0

    for i in range(1, len(data)):
        cnt += (data[i] - data[i - 1] - 1) // mid

    if cnt > m:
        left = mid + 1
    else:
        right = mid - 1

print(left)

import sys

n, m, l = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
data.append(0)
data.append(l)

data.sort()
left, right = 0, l
while left <= right:
    mid = (left + right) // 2
    if not mid:
        left = mid + 1
        continue
    cnt = 0

    for i in range(1, len(data)):
        cnt += (data[i] - data[i - 1] - 1) // mid

    if cnt > m:
        left = mid + 1
    else:
        right = mid - 1

print(left)