[BOJ] 1477 - 휴게소 세우기 (Python)

 

 

아이디어

 

매개 변수 탐색으로 휴게소가 없는 최대 구간의 최솟값을 구해 나간다.

 

 

풀이

 

휴게소가 없는 구간의 길이를 리스트 D에 저장한 후, 최대 m 길이의 구간마다 휴게소가 위치할 수 있는지 확인한다.

 

def solution():
    N, M, L = map(int, input().split())
    pos = [0]+list(map(int, input().split()))+[L]
    pos.sort()
    D = []
    for i in range(N+1):
        D.append(pos[i+1]-pos[i])
    D.sort(reverse=True)
    s = 1
    e = D[0]
    while s <= e:
        m = (s+e)//2
        cnt = sum([d//m-1*(d%m == 0) for d in D])
        if cnt > M:
            s = m+1
        else:
            e = m-1
    print(s)

solution()