[BOJ] 1477 휴게소 세우기

제가 사용한 풀이는 다음과 같습니다.

1. n개의 휴개소 위치와 0(시작점)과 l(맨 끝)을 가지는 배열을 정렬시키면 0~l까지 휴게소 위치를 차례대로 알 수 있으므로 한 위치와 다음 위치의 차가 거리가 됩니다. 이렇게 n+1개의 원소를 갖는 배열을 통해 n개의 거리를 얻을 수 있었습니다.

2. 이제 거리를 우선순위 큐에 넣어주도록 했습니다. 이때 넣을 때는 파이썬은 낮은 값이 맨 앞에 오므로 튜플 형태로 (-1*거리,거리) 이런식으로 넣어줄 수 있습니다. 그리고 이후에 탐색에 사용할 값인 나뉘기 전의 거리값과 나눈 분모도 같이 넣어주었습니다. (-거리,거리,나누기 이전의 값,나눈 분모) 이런 형식으로 값을 저장할 것이고 맨 처음에는 나누기 이전의 값과 나눈 분모는 0을 넣어주었습니다.

3. 거리가 가장 크고 나누기 이전의 값이 0 (맨 처음 넣어준 값)인 경우 두 번째로 큰 값보다 작아질 때까지 분모를 1씩 늘려가며 나눠줍니다. 그리고 나누기 전 값과 나눠진 후 그리고 나눈 분모를 우선순위 큐에 다시 푸쉬해줍니다. 이때 분수일 때라도

4. 만약 나누기 이전의 값이 0이 아닌 경우 전달받은 이전에 나눴던 분모를 +1시켜서 나눈 뒤 다시 넣어줍니다.

분모가 +1이 될 때마다 입력받은 m값을 1씩 줄여주었습니다. 이렇게 함으로써 m이 0이 되면 반복을 종료하였고 만약 우선순위 큐에 들어있는 값이 1개보다 적거나 같은 경우를 제외한 모든 경우를 만족하게 됩니다.

0개와 1개일 때는 오히려 더 간단히 계산할 수 있으므로 따로 추가해주었습니다.

# 단순히 가운데에 휴게소를 지으면 안될 듯?
# ex) 0 1000 사이에 5개 짓기 => 무지성 가운데 짓기 => 500, 250, 125... 지만 최댓값은 250
#     0 1000 사이에 200,400,600,800... 이런식으로 200,200,200,200,200 으로 최대 200

# m개의 휴게소를 지을 수 있으므로 한 구간을 m이하로 나눈 값이 특정 값 이상 또는 이하라면
# 이런 식으로 전개해야 할 것?

# 생각해보니 좌표를 구할 필요는 전혀 없고 구간별 거리만 알고있으면 됨!!
# 구간별 거리를 우선순위 큐에 넣고 구간별 거리의 최댓값을 최댓값 이전의 값?
# 두번쨰로 큰 혹은 같은 값보다 작게 만들 m이하의 n을 구하면 됨
# n으로 나눈 뒤 n번 우선순위 큐에 다시 넣어주면 될 것 아마?

from sys import stdin
from heapq import heappop,heappush

input=stdin.readline

n,m,l=map(int,input().split())
locate=list(map(int,input().split())) if n!=0 else []
locate=[0]+locate+[l]

locate.sort()
length=[]


for i in range(len(locate)-1):
    key=locate[i+1]-locate[i]
    heappush(length,(-key,key,0,0))

while m:
    try:
        none,big,before,div=heappop(length)
        nextbig=length[0][1]
        boonmo=1
        if before:
            m-=1
            boonmo=div+1
            new_val=before/boonmo
            heappush(length,(-new_val,new_val,before,boonmo))
            continue
        while big/boonmo>=nextbig and m:
            boonmo+=1
            m-=1
        new_val=big/boonmo
        heappush(length,(-new_val,new_val,big,boonmo))
    except:
        print(big//m)
        exit()

print(int(length[0][1])+(length[0][1]%1!=0))