[Baekjoon] 1477. 휴게소 세우기(Gold 4)[Python]

1477번: 휴게소 세우기

 

문제

휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

 

현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L, 현재 휴게소의 위치기 주어질 때

휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

 

풀이

M개의 휴게소를 반드시 모두 지어야 하므로, 구간의 길이를 특정하고 이를 R이라고 하겠습니다.

그렇다면 모든 구간을 R 이하로 만들기 위해 필요한 휴게소의 개수를 구할 수 있을 것입니다.

 

필요한 휴게소의 개수가 m이 될 때까지 구간의 길이를 반씩 줄여가면서 탐색하면,

휴게소 m개를 사용해 만들 수 있는 구간의 최댓값의 최솟값을 구할 수 있습니다.

🔥 넵! 이분법 문제입니다.

그러면 먼저 구간을 정해주겠습니다. 이때 주의해야 할 점이 다른 이분법 문제와 달리 해당 문제에서 초기 구간은

0이 아닌 1에서부터 L(고속도로 길이)-1 입니다.

🌹 문제에서 고속도로 끝에는 휴게소를 지을 수 없다고 나와 있기 때문입니다.

그럼 해당 구간으로 이분법 기본 코드를 작성해주겠습니다.

left, right = 1, L-1
while left <= right:
	mid = (left + right) // 2
    
    if (조건):
    	left = mid + 1
    else:
    	right = mid - 1​

이제 조건문만 구하면 됩니다.

최대 구간의 길이는 mid와 같습니다. 길이가 mid일 때, 모든 구간들을 mid 이하로 만들어줄 필요가 있습니다.

 

예를 들어, 길이가 501이고 mid가 250일 때 필요한 휴게소의 개수는 몇 개일 까요?

바로 501 // 250 = 2개 입니다. 휴게소 2개를 설치하면 250 / 250 / 1 로 구간의 길이를 mid(250) 이하로 줄일 수 있습니다.

🌹 이 때 (구간의 길이) % mid가 0일 때,(딱 나누어 떨어질 때는) 필요한 휴게소의 개수가 (구간의 길이)//mid - 1임에 유의하세요.

need = 0 # 필요한 휴게소의 개수
for d in distance:
	need += d // mid if d % mid != 0 else (d // mid - 1)

 

코드

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
rest = [0] + list(map(int, input().split())) + [L]
rest.sort()

distance = [rest[i] - rest[i-1] for i in range(1, len(rest))]

answer = L
left, right = 1, L-1
while left <= right:
  mid = (left+right) // 2

  need = 0
  for d in distance:
    need += d // mid if d % mid != 0 else (d // mid - 1)

  if need > M:
    left = mid + 1
  else:
    answer = mid
    right = mid - 1

print(answer)