[Baekjoon] 휴게소 세우기

문제

요약

L만큼의 거리 사이에 N개의 휴게소가 세워져 있다.

M개의 휴게소를 더 추가로 세워서 구간 사이의 거리 줄이려고 한다.

이미 세워진 곳과 출발지점, 끝지점에는 추가로 휴게소를 못 만든다.

휴게소를 더 세웠을 때, 구간 최대값 중 최소값은 얼마인가?

 

원본

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

1477번: 휴게소 세우기

풀이

이 문제는 얼마 전에 풀었던 프로그래머스 징검다리 문제랑 같은 문제이다.

 

https://eaz-coding.tistory.com/42

[Programmers] 징검다리

 

이전 문제는 돌을 삭제하는 것이고, 이번 문제는 돌을 추가하는 건데 왜 같아?!

라고 생각할 수 있지만 저번에 풀었던 것보다 자세히 설명해 보자면

 

임의의 거리 x, 즉 최소로 할 거리를 정했을때, 현재 있는 휴게소 사이의 거리가 이것보다 크면

두 개 휴게소 사이에 한개 이상의 휴게소를 세워 거리를 작아지게 했을 것이다.

그래서 임의의 x를 이분 탐색으로 정하고 이것을 휴게소 간의 거리와 비교해서 값을 찾아나간다.

 

여기서 주의해야할 부분이 거리가 x의 배가 되는 값일 수 있기 때문에 거리를 x로 나눈 몫을 세어준다.

 

import sys
input = sys.stdin.readline

n, m, l = map(int, input().split())
lst = [0] + list(map(int, input().split())) + [l]
lst.sort()

lw, up = 1, l-1
answer = 0

while lw <= up:
    mid = (lw+up)//2
    cnt = 0
    for i in range(1,n+2):
        if lst[i] - lst[i-1] > mid:
            cnt += (lst[i] - lst[i-1]-1) // mid

    if cnt > m:
        lw = mid + 1
    else:
        answer = mid
        up = mid - 1
        

print(answer)