취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2110번 문제인 공유기 설치이다.
문제는 아래 링크를 확인하자.

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

이 문제는 가장 인접한 두 공유기 사이의 거리를 0과 1000000000 사이에서 이분탐색(binary search)을 통해 구하는 것으로 해결할 수 있다..

두 공유기 사이의 거리를 최소 dist 이상으로 두었을 때 설치할 수 있는 최대 공유기의 개수를 구해, 그 개수와 C를 비교하는 것으로 이분탐색을 진행해나갈 수 있다.

아래는 제출한 소스코드이다.

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

int N, C;
int arr[200000];

int func(int dist) { // 간격이 dist 이상이게 최대한 설치
	int ret = 1;
	int old = arr[0];
	for (int i = 1; i < N; i++) {
		if (arr[i] - old >= dist) {
			old = arr[i];
			ret++;
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> C;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	int L = 0, R = 1000000000;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		int val = func(mid);
		if (val < C) R = mid - 1;
		else L = mid;
	}

	cout << L;
}