BOJ - 2110번 공유기 설치 문제, 이분 탐색 문제 풀이! (with C++)

이번에 풀이한 문제는 이분 탐색 알고리즘을 이용해 풀이해야 하는 문제였습니다. 

 

이분 탐색 문제를 평소에 잘 풀이해보지 않아 오랜만에 풀게 되었는데, 역시나 개념 자체에 서툴러서 이전에 정리했음에도 불구하고 풀이하는데 어려움을 느껴 다른 분들의 개념을 적극적으로 참고해 풀이하게 되었습니다.

 

문제 링크는 여깄습니다! 😁

2110번: 공유기 설치

---

2110번 문제 설명 

우선 문제는 도현이가 가진 N개의 집에 C개의 공유기를 설치하는데, 공유기를 최대한 떨어뜨려서 설치하고 싶을 때 공유기 간의 최소 간격의 최댓값을 구하는 문제입니다.

 

최소 간격의 최댓값이라는 말이 조금 복잡하게 느껴져서 이해하기 힘들었는데, 이는 공유기를 배치했을 때 공유기 간의 간격 중 최솟값이 있을 것이고 이 값을 최대한으로 할 때, 그 값이 무엇인가?? 를 묻는다고 생각하면 됩니다.

 

다시 한 번 그림으로 설명해 보겠습니다.

1, 2, 4, 8, 9번 위치에 도현이의 집이 위치해있다!!

집이 위와 같이 일차원 좌표에 배치되어 있을 때, 다음과 같이 3개의 공유기를 설치를 한다고 가정해 보도록 하겠습니다.

1번, 4번, 8번 집에 공유기를 배치한다면??

1번, 4번, 8번 위치의 집에 공유기가 설치되었을 때, 공유기 간의 간격은 각각 3, 4가 되므로 '공유기 간의 간격의 최솟값'은 3이 되는 것이고, 우리는 위와 같이 3개의 공유기를 배치했을 때 이 '최소 간격'의 최댓값을 구하는 것이 됩니다!!

 

출력은 계산한 최댓값을 출력하면 됩니다.

---

풀이 과정

저는 위 문제에 대한 이해를 토대로 다음과 같이 생각한 이후 문제 풀이를 진행했습니다.

◆  이분 탐색에 대해 기준으로 삼아야 하는 값은 거리이다.
◆  거리에 따라 설치 가능한 공유기 대수가 바뀌고, 설치할 수 있는 공유기 대수에 따라 탐색을 진행해야 되기 때문이다.
◆  추가적으로 '최대의 거리'를 구하는 것이 목표이기 때문에 upper bound 형식으로 이분 탐색을 적용해야 한다. (lower bound는 처음으로 key 값보다 작지 않은 값을 반환, upper bound는 처음으로 key 보다 큰 값을 반환)

 

이분 탐색을 적용하는 이유는 적용하는 '최소 간격(공유기 간의 간격)'에 따라서 설치 가능한 '공유기의 수'가 달라지고, 설치 가능한 공유기의 수가 c를 넘어서지 못하는 경우는 조건을 만족하지 않는다 판단하여, 탐색 범위를 점점 좁혀서 (최소 간격) 탐색해 나아가는 과정을 반복하기 때문입니다.

 

그중에서도 upper bound 형식으로 이분 탐색을 진행해야 하는 이유는 조건을 만족하는 값 중에서 최댓값을 찾는 것이 목적이기 때문이라고 할 수 있습니다. 

 

이분 탐색에 대한 추가적인 개념은 아래의 글에 간다 하게 정리해 두었습니다.

https://blog.naver.com/book541/222679244116

[알고리즘] 이분 탐색 (Binary Search) 정리 및 lower_bound, upper_bound 함수

---

제출한 소스 코드 (C++)

/*
	Date: 2022/08/28
	Brief:
	이분 탐색
	Reference:
	https://st-lab.tistory.com/277
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, c;
vector<int> homeSite;

int installRouter(int);

// upper bound 양식에 따른 이분 탐색 알고리즘을 구현해야 한다.
// 조건을 만족하는 최댓값을 선택해야 하기 때문이다.
int bipartiteSearch() {
	// lo: 거리의 최솟값, hi: 거리의 최댓값 (1개만 설치하는 경우?)
	int lo = 1, hi = homeSite[n-1] + 1;

	while (lo < hi) {
		int mid = (lo + hi) / 2;
		//cout << lo << " " << hi << endl;
		if (installRouter(mid) < c) {
			// 설치 가능한 공유기 숫자가 적은 경우 거리를 줄여야
			hi = mid;
		}
		else {
			// 설치 가능한 공유기 숫자가 많은 경우 거리를 늘려도 된다.
			lo = mid + 1;
		}

	}
	// hi는 상한선이므로
	return hi - 1;
}

// 주어진 최소 간격에 대해 설치 가능한 공유기 수를 구하는 함수
int installRouter(int dis) {
	int cnt = 1;

	int prev = homeSite[0];

	for (int i = 1; i < n; i++) {
		int cur = homeSite[i];
		// 이전에 설치한 공유기 위치가 dis보다 작은 경우 현재 집에는 공유기 설치가
		// 불가능하다.
		if (cur - prev < dis)
			continue;
		// 공유기 설치가 가능한 경우 prev 집 위치를 변경하고, 공유기 수를 count
		prev = cur;
		cnt++;
	}

	return cnt;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		homeSite.push_back(tmp);
	}
	sort(homeSite.begin(), homeSite.end());
	cout << bipartiteSearch();

	return 0;
}

/*
n개의 집의 좌표가 주어졌을 때, c개의 공유기를 최소의 간격으로 설치할 때
이 간격이 가질 수 있는 최대를 구한다.

* 이분 탐색으로 풀이해야 하는 문제이다.
* 이분 탐색에 대해 기준으로 삼아야 하는 값은 거리이다.
* 거리에 따라 설치 가능한 공유기 대수가 바뀌고
* 설치할 수 있는 공유기 대수에 따라 탐색을 진행해야 되기 때문이다.
* 추가적으로 최대의 거리를 구하는 것이 목표이기 때문에 upper bound 형식으로 이분 탐색을 적용해야 한다고 함.

*/

 

Reference

아래의 글에서 이분 탐색 방식이 어떻게 적용되어 해당 문제를 풀이하는 느낌인지 확실하게 이해할 수 있었습니다.

https://st-lab.tistory.com/277

[백준] 2110번 : 공유기 설치 - JAVA [자바]