ALGORITHM/BOJ
[BOJ] 1477번 휴게소 세우기 (C++)
yegyeom
2021. 12. 21. 11:38
문제 (https://www.acmicpc.net/problem/1477)
1477번: 휴게소 세우기
첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.
www.acmicpc.net
이분 탐색 문제이다. 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
[소스코드]
