[Gold IV] 휴게소 세우기 - 1477 (이분탐색)

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

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

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

-풀이 방법

- 접근 방법

휴게소들을 정렬하여 이분탐색을 해야겠다는 생각은 했는데, 확신은 가지지 못하였고 알고리즘 분류를 보고도 아이디어가 생각나지 않아서 구글링으로 풀이를 참고하여 풀었다.

- 풀이 방법
1. 휴게소 사이의 거리를 최소한으로 줄이기 위해 각각의 휴게소의 거리를 찾아야 했기 떄문에 오름차순 정렬
2. 휴게소 사이의 거리가 이분탐색을 통한 mid값보다 클 경우 mid값으로 나눈 몫만큼 휴게소를 설치
3. 휴게소 개수가 주어진 M개를 초과하면 mid값 증가, 그 반대의 경우 mid값 감소
4. 직전에 구한 mid값을 answer에 저장
5. 이분탐색 범위가 끝난 후, 최종적으로 구해진 answer 출력

'''
이분 탐색
'''

N, M, L = map(int, input().split())
# 오름차순 정렬 : 휴게소 사이의 거리 중 최대 거리를 찾아야 하므로 + 이분탐색 해야해서
arr = sorted([0] + list(map(int,input().split())) + [L]) 

# 휴게소의 최소, 최대 거리
start = 1
end = L-1
answer = 0
# 이분탐색
while start <= end:
    # 휴게소 없는 구간 값 저장
    mid = (start + end) // 2 

    # 휴게소 설치 수
    shelter_cnt = 0 
    for i in range(1, len(arr)):
        # 해당 휴게소 사이 거리가 mid보다 클 경우 나눈 몫 만큼 휴게소 설치
        if mid < arr[i] - arr[i-1]:
            shelter_cnt += (arr[i] - arr[i-1] - 1) // mid
    
    # 설치할 수 있는 휴게소 개수를 넘은 경우 mid 증가
    if shelter_cnt > M: 
        start = mid + 1
    else:
        end = mid - 1
        answer = mid  # 현재까지의 최솟값 저장
        
print(answer)