[BOJ/c++] 2110- 종이의 개수

문제

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

2110번: 공유기 설치

해설

공유기의 갯수가 아니라 공유기가 설치되는 거리를 이분탐색으로 탐색하면 되는 문제였다. 완전탐색으로 할 경우엔 1부터 1000000000까지 가능하므로 시간초과가 나고 이분탐색으로 탐색시 logN이므로 시간안에 풀수있다.

공유기 거리가 늘어날수록 공유기 갯수가 줄어들므로 c보다 공유기 갯수가 적을때 거리(이분탐색하고자 하는 값)를 줄여가며 구현한다.

코드

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

int n, c;
int x[200001];

int main () {
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
   }

	sort(x, x + n);
	int high = x[n-1]-x[0], low = 1;
	int result;
	while (high >= low) {
		int mid = (high + low) / 2;

		int cnt = 1, lastLocate = x[0];
		for (int i = 1; i < n; i++) {
			int d = x[i] - lastLocate;
			if (mid <= d) {
				cnt++;;
				lastLocate = x[i];
			}

		}
		if (cnt >= c) {
			result = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}

	}
	cout << result;
}