[2110] 공유기 설치 C++

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

2110번: 공유기 설치

- 이분탐색 (cnt >= C)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, C;
	int arr[200001];

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

	sort(arr, arr + N);

	int left = 0;
	int right = arr[N - 1];

	int answer = -21e8;

	// 첫집은 무조건 설치해야 최대거리 구할수 있음
	while (left <= right) {
		int before = 0;
		int cnt = 1;

		int middle = (left + right) / 2;

		for (int i = 1; i < N; i++) {
			if (arr[i] - arr[before] >= middle) {
				before = i;
				cnt++;
			}
		}


		// cnt == C가 아니라 cnt >= C가 맞음 (최소길이만 비교하면 되기 때문)
		if (cnt >= C) {
			if (middle > answer)
				answer = middle;

			left = middle + 1;
		}

		else {
			right = middle - 1;
		}

	}

	cout << answer;

	return 0;
}

 

- dfs (시간초과)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, C;
int arr[200001];
int path[200001];
int MAX = -21e8;

void dfs(int le, int st) {
	if (le == C) {
		int MIN = 21e8;

		for (int a = 1; a < C; a++) {
			MIN = min(MIN, (path[a] - path[a - 1]));
		}

		if (MIN > MAX)
			MAX = MIN;

		return;
	}

	for (int i = st; i < N; i++) {
		path[le] = arr[i];
		dfs(le + 1, i + 1);
	}
}

int main() {

	cin >> N >> C;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);

	path[0] = arr[0];
	dfs(1,1);
	
	cout << MAX;


	return 0;
}