[백준 / BOJ] 2110번: 공유기 설치

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

2110번: 공유기 설치

 

---

 

 

문제

---

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

출력

---

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

예제 입력

---

5 3
1
2
8
4
9

 

예제 출력

---

3

 

코드 

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v;
int n, c;

int solve() {
	int s, e;
	s = 0;
	e = v[n - 1];
	while (s <= e) {
		int gap = (s + e) / 2;
		int cnt = 1;
		auto idx = v.begin();
		for (auto i = idx + 1; i < v.end(); i++) {
			if (*i >= *idx + gap) {
				idx = i;
				cnt++;
			}
		}
		if (cnt >= c) s = gap + 1;
		else e = gap - 1;
	}
	return e;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}

	sort(v.begin(), v.end());
	cout << solve();
	return 0;
}

 

 

 

---

 

 

이분탐색 문제...어렵다... while문 조건식과 끝처리를 어떻게 해야하는지 이해가 잘 안된다... 

이 문제도 왜 이분탐색으로 풀 수 있는지 이해를 잘 못했었다. 

암튼 start와 end 변수를 공유기 설치 거리로 생각해야 한다. 설치 간격이 1일 수도 있고, 아주 길 경우 입력으로 주어진 가장 큰 집 좌표만큼 클 수도 있다. 나는 처음에 start 값을 입력으로 주어진 가장 작은 집 좌표로 두고 시작했었는데 이러면 공유기가 설치되는 간격이 1처럼 작은 경우를 고려할 수 없다.

그리고 끝점처리... while문 종료 조건... 좀 더 고민해보기로...

 

 

+복습 문제

https://minpaeng.tistory.com/177?category=900801 

https://minpaeng.tistory.com/178

https://minpaeng.tistory.com/179