[백준/알고리즘] 2110번 공유기 설치 (실버 2)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 2110번

 

집의 좌표 n개가 수직선 상에 있다. 공유기의 개수 c개가 주어졌을 때, 가장 인접한 공유기의 거리가 최대로 하는 공유기 사이의 거리를 출력하시오.

 

풀이 알고리즘 : 이분탐색

 

예제 입력 1번을 예로 들어 보자.

 

예제 입력 1 추가 설명

문제에서, 집의 좌표는 1, 2, 4, 8, 9이고, 첫번째 그림은 [1, 2, 9]를 선택했을 경우, 두번째 그림은 [1, 4, 8]을 선택했을 경우이다.

각각의 경우에서 가장 인접한 두 공유기 사이의 거리는 1과 3이다. 문제에서는 이 거리의 최대값을 구하여서 출력하라는 것이다.

 

그래서 이분탐색을 통해, 각각의 케이스에서 최소 거리를 구하고, 그 거리를 기준으로 공유기를 설치했을 때, 총 몇개의 공유기를 설치할 수 있는가를 통해 점점 범위를 줄여나갈것이다.

 

이분탐색의 범위의 최솟값은 1이고, 최댓값은 가장 좌표가 큰 집과 가장 좌표가 작은 집의 차이이다.

 

이분탐색 결과, 현재 공유기를 설치한 집의 개수가 c보다 크다면, 최소 거리가 너무 작은 것이다.

현재 설치한 집의 개수가 c와 같거나 더 많다면, 이는 정답이 될 수 있고, 문제에서 해당 거리의 최댓값을 구하라고 요청했기 때문에, 이 값을 저장하고 최소 거리를 더 늘려서 탐색을 진행한다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	// 집의 개수, 공유기의 개수, 최대 거리(출력값)
	int n, c, ans = 0;
	cin >> n >> c;
	// 집의 좌표
	int dir[n] = {0};
	for(int i = 0; i < n; i++) cin >> dir[i];
	// 좌표 정렬
	sort(dir, dir + n);

	// 최소 거리를 이분탐색으로 확인
	int le = 1, ri = dir[n - 1] - dir[0];
	while(le <= ri) {
		// 이번 시행에서의 최소 거리
		int mid = (le + ri) / 2;
		// mid를 기준으로 했을 때, 설치 한 공유기의 개수
		// 가장 최근에 방문한 집의 좌표
		int cnt = 0, prev;

		for(int i = 0; i < n; i++) {
			if(i == 0) { prev = dir[0]; cnt++; continue; }
			if(mid <= dir[i] - prev) {
				prev = dir[i];
				cnt++;
			}
		}

		if(cnt < c) {
			// 설치한 공유기가 부족한 경우
			ri = mid - 1;
		} else {
			// c개 이상 설치할 수 있는 경우
			if(ans < mid) ans = mid;
			le = mid + 1;
		}
	}

	cout << ans;
	
	return 0;
}