[백준] 1477 - 휴게소 세우기

문제 링크

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

문제 요약

다솜이는 현재 N개의 휴게소를 가진 고속도로에서 M개의 새로운 휴게소를 더 세우려고 합니다. 목표는 휴게소가 없는 구간의 길이의 최댓값을 최소화하는 것입니다.

• 휴게소는 고속도로의 시작과 끝에는 세울 수 없고, 기존 휴게소가 있는 곳에도 새로 세울 수 없습니다.
• 휴게소는 정수 위치에만 세울 수 있습니다.
• N개의 기존 휴게소와 M개의 새로운 휴게소가 주어질 때, 휴게소가 없는 구간의 최댓값을 최소화했을 때의 값을 구하는 문제입니다.

푼 방법

 

• 휴게소 간 구간 길이를 계산하고, 해당 구간에 새로운 휴게소를 배치합니다.
• 이진 탐색을 통해 휴게소가 없는 구간의 최댓값을 최소화하는 값을 찾습니다.

 

정답 코드

import sys
n, m, l = map(int, sys.stdin.readline().split())

hue = list(map(int, sys.stdin.readline().split()))

hue.sort()

dist = []
if n>0:
    for i in range(n+1):
        if i==0:
            dist.append(hue[0])
        elif i==n:
            dist.append(l-hue[-1])
        else:
            dist.append(hue[i] - hue[i-1])
else:
    dist.append(l)
    
def chk(mid):
    tmp = 0
    for i in range(len(dist)):
        tmp += (dist[i]-1)//mid
    return tmp <= m

s = 1
e = l

while s<=e:
    mid = (s+e)//2
    if chk(mid):
        e = mid-1
    else:
        s = mid+1

print(s)

배웠던 부분

• 이전에 풀었던 케이크 자르기와 유사한 이분탐색 문제임.
• 답을 제출하고 다른 사람들의 풀이를 보니 우선순위큐로 해결한 케이스도 있음
  • 매순간 가장 큰 경우를 큐에서 얻고 다음 요소보다 작아질 때 까지 나누는 수를 증가시키며 나눔
  • 나누는 수가 m이 될 때 까지 반복