[G4] 백준 1477번 휴게소 세우기 C++ 이분 탐색, 매개 변수 탐색

리뷰

 

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

이분 탐색을 통해 휴게소를 m개 세웠을때 휴게소간 거리가 최소가 되게 만들어 주는 문제

 

전역 변수

1. n, m, l : 현재 설치된 휴게소의 개수n, 추가로 설치해야 하는 휴게소의 개수m, 도로의 길이 l
2. ans : 휴게소간 거리가 최소가 되는 경우의 정답
3. lst : 설치되어있는 휴게소의 정보를 담은 정수형 배열

 

함수

없음

 

 

문제풀이

1. n, m, l값을 입력 받고, n개의 수를 lst배열에 입력 받은 뒤 lst배열을 정렬 해준다.
2. 만약 n이 0일 경우 ans는 l / (m + 1)을 올림 처리한 값으로 ans에 저장한다.
3. n이 0이 아닐 경우 이분탐색을 진행해 준다.
4. 왼쪽 탐색 시작은 left = 1로, 오른쪽 탐색 시작은 최대 도로 보다 두배 큰 right = 2000으로 초기화 했다.
5. left가 right보다 작거나 같을 경우 이분탐색을 계속 진행해 준다.
6. mid를 l + r을 2로 나눈 몫으로 설정해 준다. cur은 현재 위치이고, install은 설치한 개수로 모두 0으로 초기화 한다.
7. 이미 설치된 휴게소를 순회한다, 현재 위치에서 i번째 휴게소에 mid거리로 도착할 수 있다면 cur을 휴게소로 바꿔준다.
8. 만약 mid거리로 도착할 수 없다면 cur에 mid를 더해주고 install을 1증가시켜준다.
9. 모든 휴게소에 대한 탐색을 마치면 cur은 마지막 휴게소의 위치에 있을 것이다.
10. 마지막 휴게소의 위치에서 도로의 끝인 l까지 가는 길도 똑같이 진행해 준다.
11. 만약 install이 m보다 작거나 같을 경우 right을 mid - 1로, ans를 mid와 ans중 작은 값으로 최신화 해준다.
12. 만약 install이 m보다 클 경우 left를 mid + 1로 바꾸어 준다.
13. 모든 이분 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

참고 사항

mid가 휴게소간 거리를 의미하며, 이 값이 최소가 되는 값을 구하는 것이 목적이다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int n, m, l, ans = 1e9;
int lst[50];

int main() {
	cin >> n >> m >> l;
	for (int i = 0; i < n; i++) cin >> lst[i];
	sort(lst, lst + n);

	if (!n) ans = ceil((double)l / (m + 1));
	else {
		int left = 1, right = 2000;
		while (left <= right) {
			int mid = (left + right) / 2;
			int cur = 0;
			int install = 0;

			for (int i = 0; i < n; i++) {
				while (cur + mid < lst[i]) {
					cur += mid;
					install++;
				}
				cur = lst[i];
			}

			while (cur + mid < l) {
				cur += mid;
				install++;
			}

			if (install <= m) {
				right = mid - 1;
				ans = min(ans, mid);
			}
			else left = mid + 1;
		}
	}
	cout << ans;
}