[BOJ]1477번: 휴게소 세우기

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

---

nnnyeong님 풀이를 참고하여 해결하였습니다.

 

이분 탐색을 활용한 결정 문제입니다.

 

결정 조건은 "휴게소 M개 사이의 거리를 distance 로 하였을 때 몇 개의 휴게소를 새로 세울 수 있느냐" 입니다.

 

그리고 이 distance 값을 이분탐색으로 찾으면서 M개 이하를 세울 수 있는 distance의 최솟값을 구하면 됩니다.

 

M개 이하라고 한 이유는, M개 미만의 휴게소를 세워서 distance 조건을 만족할 수 있다면 휴게소를 한 개 씩 더 추가해서 distance를 더 줄일 수 있고 이렇게 늘려가다보면 결국 딱 M개의 휴게소를 세울 때의 거리가 정답 후보가 됩니다. 그 정답 후보들의 최솟값을 구해주면 됩니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1477.java