[BOJ] 1477번 휴게소 세우기 (C++)

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

1477번: 휴게소 세우기

이분 탐색 문제이다. vector에 휴게소의 시작점과 끝점(0, l), 입력받은 위치들을 넣어주고 정렬한다. 1 ≤ 휴게소의 위치 ≤ l - 1이므로 start = 1, end = l - 1로 설정했다. 휴게소 사이의 거리인 mid를 구하고 기존 휴게소 사이에 몇 개의 휴게소를 설치할 수 있는지 계산한다.

 

이때, dist % mid 값이 0이라면 휴게소 위치가 겹치는 것이므로 개수를 하나 빼야 함!

예를 들어, 기존 휴게소 위치가 201 - 411이고 mid 값이 70이라면? 둘 사이의 거리가 210이므로 설치 가능한 휴게소의 개수(dist / mid)는 3이지만 실제론 201 - 271 - 341 - 411 가 되므로 개수는 2가 맞는 것!

 

설치 가능한 휴게소의 개수가 m보다 크다면? 휴게소 사이의 거리를 늘려야 하므로 start = mid + 1

설치 가능한 휴게소의 개수가 m보다 작거나 같다면? 휴게소 사이의 거리를 최소로 하기 위해 end = mid - 1

---

[소스코드]

---

2021-12-20

Gold 4

- 이분 탐색

- 매개 변수 탐색