BOJ : 휴게소 세우기 [1477]

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

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

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

---

아이디어

1.휴게소설치 목록에 0과 전체 고속도로 길이를 추가시켜준다.
2. 해당 휴게소와 이전 휴게소의 간격을 구하고 가장 큰 간격 순으로 휴게소를 하나씩 설치 시켜준다.
3. M개를 다 지을 때까지 반복해주고 간격이 가장 큰 부분을 찾아 출력해준다.

---

코드

Mine(못풀음)

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split()))
rest_area = list(map(int, input().split()))
rest_area.append(0)
rest_area.append(L)
rest_area.sort()

...?

개선사항

left, right, mid 기준을 무엇으로 잡아야할지 모름
설치한 휴게소 개수 구하는 것도 어떻게 해야할지 모름

---

Clone

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
stations = list(map(int, input().split()))
stations.append(0)
stations.append(L-1)
stations = sorted(stations)

left = 0
right = L-1
while left <= right:
    mid = (left+right) // 2
    count = 0 # 설치한 휴게소의 수
    for i in range(1, len(stations)):
        if stations[i] - stations[i-1] > mid:
            count += (stations[i] - stations[i-1] -1)//mid

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

print(answer)

출처 : https://kimmeh1.tistory.com/250

자세한 설명 : https://kau-algorithm.tistory.com/136

개선사항