[Python] 백준 1477 - 휴게소 세우기 문제 풀이

Overview

BOJ 1477번 휴게소 세우기 Python 문제 풀이
분류: Binary Search (이분탐색)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

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

    stations.sort()
    dists = list(stations[i + 1] - stations[i] for i in range(len(stations) - 1))

    res = 0
    start, end = 1, L
    while start <= end:
        mid = start + (end - start) // 2
        cnt = 0
        for dist in dists:
            if dist > mid:
                cnt += (dist - 1) // mid

        if cnt <= M:
            res = mid
            end = mid - 1
        else:
            start = mid + 1

    print(res)


if __name__ == "__main__":
    main()

이분탐색을 이용하여 새로 설치할 휴게소 거리를 정하고, 해당 거리에서 설치 가능한 휴게소 개수가 M개 이하면 결과값으로 업데이트한다.