[백준] 이진 탐색 - 1477 휴게소 세우기

문제 <휴게소 세우기>

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

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

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

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

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

---

입력

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

---

출력

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

---

제한사항

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

---

풀이

• 고속도로의 처음과 끝에는 휴게소를 설치하지 못하므로 따로 추가하고 정렬하였다.
• 이진 탐색으로 휴게소의 설치 간격을 줄이거나 늘려가며 문제를 해결해야겠다고 생각했다.
• 설치한 휴게소의 개수가 M보다 크면 간격을 늘리고, M보다 작으면 간격을 줄였다.

import sys

input_data = sys.stdin.readline

N, M, L = map(int, input_data().split())
loc = list(map(int, input_data().split()))
loc.append(0)       # 고속도로의 끝에는 휴게소 세울 수 없으므로 추가해 주기
loc.append(L)
loc.sort()


def Binary_search(loc, start, end, M):
    result = 0
    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        for i in range(len(loc)-1):
            if loc[i+1] - loc[i] > mid:     # 사이의 거리가 휴게소 설치 간격보다 클 경우
                cnt += (loc[i+1] - loc[i] - 1) // mid
        if cnt > M:     # 설치된 휴게소의 개수가 M보다 클 때
            start = mid + 1     # 휴게소 설치 간격 늘리기
        else:
            result = mid        # 결과값 갱신
            end = mid - 1       # 휴게소 설치 간격 줄이기
    return result


print(Binary_search(loc, 1, L-1, M))

위 코드에서 예제에 대한 정답이 맞는 것을 확인했지만 런타임 에러가 발생했는데 그 이유는 휴게소 사이의 거리와 mid를 비교하는 for문 때문이었다.

for i in range(1, len(loc)):
    if loc[i] - loc[i-1] > mid:     # 사이의 거리가 휴게소 설치 간격보다 클 경우
        cnt += (loc[i] - loc[i-1] - 1) // mid

이와 같은 코드로 변경해 주었을 때는 해결이 되었다..! 두 코드의 작동이 동일한 것 같다고 생각하는데 내 코드에서 런타임 에러가 뜨는 이유가 궁금하다.

두 번째로 의문이었던 점은 휴게소를 정확히 M개를 설치해야 하는데 설치된 휴게소의 개수가 M보다 작거나 같을 때 result를 갱신해 주는 점이었다.

이는 start와 end를 조정하면서 마지막에는 휴게소 M개를 설치할 수 있는 구간의 최댓값의 최솟값이 도출되기 때문이었다.

수정한 전체 코드는 다음과 같다.

import sys

input_data = sys.stdin.readline

N, M, L = map(int, input_data().split())
loc = list(map(int, input_data().split()))
loc.append(0)       # 고속도로의 끝에는 휴게소 세울 수 없으므로 추가해 주기
loc.append(L)
loc.sort()


def Binary_search(loc, start, end, M):
    result = 0
    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        for i in range(1, len(loc)):
            if loc[i] - loc[i-1] > mid:     # 사이의 거리가 휴게소 설치 간격보다 클 경우
                cnt += (loc[i] - loc[i-1] - 1) // mid
        if cnt > M:     # 설치된 휴게소의 개수가 M보다 클 때
            start = mid + 1     # 휴게소 설치 간격 늘리기
        else:
            result = mid        # 결과값 갱신
            end = mid - 1       # 휴게소 설치 간격 줄이기
    return result


print(Binary_search(loc, 1, L-1, M))

아직 이진 탐색으로 문제를 푸는 방식이 어색한 것 같아 조금 더 연습이 필요하다!

이진 탐색 문제는 수직선으로 길게 연결된 형태에서 하나씩 설치해 가는 형태의 문제가 많이 출제되는 것 같다.

---

문제를 보고 어떤 알고리즘을 사용해야 할지 판단하는 연습이 필요하다!

 

 

 

 

 

1477번: 휴게소 세우기