백준1477(휴게소 세우기) - 참고 해결

휴게소 세우기

 

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

 

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

 

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

---

이분탐색 문제였는데 이분 탐색을 잘 못해서 다른 문제를 좀 풀어보고 풀어보았다.

이분 탐색의 핵심은 어떤 걸 탐색할 것인가이다.

여기에서는 거리를 가지고 탐색을 하였다.

어떤 거리의 차이를 두고 휴게소를 설치할 것인가를 탐색하였다.

일정 거리를 두고 휴게소를 설치 하였을 때 추가되는 휴게소의 개수를 파악하고 이를 M과 비교하는 방식으로 구하였다.

그 개수를 구하는 방식은 현재 각 휴게소의 거리를 구하고 그 안에서 일정 거리를 두고 휴게소를 몇개가 설치되는 가를 파악하였다.

다만 16%에서 zerodivision 에러가 발생하여서 수정한 부분이 있는데

그 부분 이외에도 44%에서 틀리는데 이 부분은 최소값을 1로 하면 해결이 되었다.

하지만 최소값을 0으로 했을 때와 1로 했을 때 차이를 정확히 모르겠다.

import sys
input = sys.stdin.readline

N, M, L = map(int,input().split())

rest_areas = list(map(int,input().split()))
# 거리를 구하기 위해서 고속도로의 각 끝을 넣어준다.
rest_areas.extend([0,L])
rest_areas.sort()

# 최소값은 차이가 1 최댔값은 L
l = 1
r = L

while l <= r:
    mid = (l + r)//2
    cnt = 0
    for i in range(1,N+2):
        # 각 거리에 몇개의 휴게소가 들어가는지 확인
        dist = rest_areas[i] - rest_areas[i-1]
        # 딱 나누어 떨어지면 휴게소가 하나 줄어들기 때문에
        if dist % mid:
            cnt += dist//mid
        else:
            cnt += (dist//mid - 1)
    
    if cnt > M:
        l = mid + 1
    else:
        r = mid - 1
print(l)