[백준] 1477(파이썬) - 휴게소 세우기

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

1477번: 휴게소 세우기

• 이 문제를 읽고 처음 든 생각은 이분 탐색으로 풀어야겠다 였다.
• 처음에는 입력받은 휴게소위치에 0과 l 값을 넣어줘서 각각 휴게소 사이의 거리들을 구해서 오름차순 정렬한 뒤, 
  각각 거리들의 차 만큼과 이분 탐색한 값을 비교해주면서 구현하였다.
• 이분 탐색으로 풀어야 하는데 카운트를 어떻게 할지가 문제였는데, 거리에 맞게 지어야 하므로 거리를 mid 값으로 나눈 값을 카운트해서 m개가 되면 그 mid값이 처음 나왔을 때가 최대이면서 최소인 값이라고 생각했다.

import sys
input = sys.stdin.readline

n,m,l = map(int,input().split())
data = list(map(int,input().split()))

data.append(0)
data.append(l-1)
data.sort()


start = 0
end = data[-1]
while start <= end:
    cnt = 0
    mid  = (start+end) // 2
    for i in range(1,len(data)):
        if (data[i]-data[i-1]) > mid:
        # 이 부분이 이문제에서 핵심인 부분!
            cnt += (data[i]-data[i-1] - 1)//mid
    
    if cnt > m:
        start = mid + 1
    else:
        end = mid - 1
        answer = mid

print(answer)