[C] 백준 - 2110번: 공유기 설치

5월 15일(수) - 이분 탐색(2110번)

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

---

최초 생각 정리

---

문제점

---

풀이

(풀이출처 -> https://wonsjung.tistory.com/68)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int N, C;
int arr[200001];

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2)
	{
		return 1;
	}
	else if (num1 < num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

int is_on(int x)
{
	int count = 1;
	int prev = arr[0];
	for (int i = 1; i < N; i++)
	{
		if (arr[i] - prev >= x)
		{
			count++;
			prev = arr[i];
		}
	}

	if (count >= C)
	{
		return 1;
	}

	return 0;
}

int main(void)
{
	scanf("%d %d", &N, &C);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}

	qsort(arr, N, sizeof(int), compare);
	
	int left = 1;
	int right = arr[N - 1] - arr[0];
	int answer = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (is_on(mid))
		{
			answer = MAX(answer, mid);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	printf("%d", answer);
	return 0;
}

---