[Baekjoon/백준] 2110번: 공유기 설치(C/C++)

단계별로 풀어보기 21단계(이분 탐색) 5번 문제

https://www.acmicpc.net/step/29

이분 탐색 단계

---

백준 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)가 한 줄에 하나씩 주어진다.

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

힌트: 공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

---

접근 방법

이번 문제는 집의 개수 N과 공유기 개수 C를 입력받고, 이후 각 집의 좌표 xi를 입력받아 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 문제다.

가장 인접한 두 공유기 사이의 최대 거리라고 하니까 조금 헷갈리지만, 위 예제와 힌트를 보면 조금 쉽게 이해할 수 있다. 예제처럼 1 2 4 8 9에 집이 위치할 때, 1 4 8 혹은 1 4 9로 공유기를 설치하면 1과 4 사이의 거리가 3으로 가장 인접하면서, 다른 공유기 3개를 설치했을 때(1 2 4, 1 8 9 ... 등)의 경우들의 가장 인접한 거리 중에서는 최댓값이다. 그래서 3이 출력되는 것이다.

이번 문제를 풀기위해서는 입력받은 집 간의 거리가 오름차순으로 정렬되서 순서대로 있어야한다. 따라서 sort를 통해서 배열을 정렬하고, 이후 공유기를 설치했을 때의 거리를 구해야한다. 거리는 단순하게 현재 위치에서 이전 설치 위치까지의 거리를 빼면된다. 하지만 처음 이전 설치 위치는 첫번째 집인 것이 중요하다. 그래야 최대 거리를 구할 수 있기 때문이다.

이제 이분 탐색을 통해서 집 간 거리의 중간값과 앞에서 구한 거리를 비교했을 때, 거리가 중간 값보다 크다면 그 위치에 공유기를 설치하고 다음 위치로 이동한다. 이후 설치한 개수가 C보다 크거나 같다면 더 큰 값을 탐색해보고, 작다면 더 작은 값을 탐색해본다. 이를 반복하면 문제를 해결할 수 있다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 200000

int house[MAX];

int main(int argc, char *argv[]) {
	int N, C, previous, count, start, end, mid, result = -1;
	cin >> N >> C;

	for (int i = 0; i < N; i++)
            cin >> house[i];

	sort(house, house + N);

	start = 0;
	end = house[N - 1];

	while (end >= start) {
		mid = (start + end) / 2;
		previous = 0;
		count = 1;
		for (int i = 1; i < N; i++)
			if (house[i] - house[previous] >= mid) {
				previous = i;
				count++;
			}

		if (count >= C) {
			start = mid + 1;
			if (result < mid)
				result = mid;
		}
		else
			end = mid - 1;
	}

	cout << result << endl;

	return 0;
}

---

결과

백준 제출 결과