[알고리즘] C++ 백준 2110 공유기 설치

백준 2110

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

2110번: 공유기 설치

풀이 전 나의 생각

도현이의 집 N개의 좌표에 공유기를 설치할 것이다.

단, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치하고

이 때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 값을 구해야한다.

 

조건

- N (2 ≤ N ≤ 200,000)

- C (2 ≤ C ≤ N)

- xi (0 ≤ xi ≤ 1,000,000,000)

 

과정

N을 20만 번 탐색하며 집 사이의 최대 거리 10억을 하나하나 검사하기엔

탐색횟수가 너무 많아지기 때문에 이분탐색을 사용하여 풀이를 진행해야 한다.

 

가장 인접한 두 공유기 사이의 거리를 구하면서

최대한 거리를 크게 하여 설치한다는 의미는

결국, 공유기 사이마다의 거리를 균등하게 설정한다는 것과 같다.

 

ex)

1, 2, 8 => 사이의 거리 1, 6 , 인접한 두 사이의 거리 1 (X)

1, 4, 8 => 사이의 거리 3, 4 , 인접한 두 사이의 거리 3 (O)

-> 공유기 사이의 거리가 가장 큰 값을 구하는게 아닌, 인접한 두 사이의 거리의 최대를 구하는 것이다.

 

따라서 공유가 사이의 거리를 균등하게 해줄 수 있는 거리를 얻기 위해

중간 거리를 설정 후, 탐색을 시작하며 값을 구해나가야 한다.

 

여기서 중간 거리는 집과 집사이의 최소 거리와 최대 거리의 중간값을 의미하며

동시에 집과 집사이의 거리를 판단하는 기준값이 된다.

 

1. 중간 거리를 구하기 위해 시작과 끝을 설정한다.

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

start = 최소 거리

end = 집의 좌표 끝 - 집의 좌표 시작 -> 현재 나올 수 있는 최대 집 사이의 거리

 

2. 이분탐색에 필요한 중간 거리, 이전 집의 좌표, 현재 공유기 설치 현황을 설정한다.

int mid = (start + end) / 2;
int prev = house[0];
int set = 1;

 

3. 집 사이의 거리가 중간 거리보다 같거나 크다면 공유기를 설치해주고, 이전 집 좌표를 갱신한다.

for (int i = 1; i < N; i++)
{
	if (house[i] - prev >= mid)
	{
		set++;
		prev = house[i];
	}
}

 

4. 공유기의 설치 개수가 많다면 중간 거리를 늘려주고, 적다면 중간 거리를 줄여준다.

if (set >= C)
{
	ans = max(ans, mid);
	start = mid + 1;
}
else
{
	end = mid - 1;
}

설치 개수가 많다는 의미는 현재 중간 거리가 작아 많이 설치할 수 있다는 것이고

설치 개수가 적다는 의미느 현재 중간 거리가 커서 많이 설치할 수 없다는 것이다.

따라서 중간 거리를 줄이거나, 늘리며 최적의 값을 찾아나가야 한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int house[200001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, C, ans = 0;

	cin >> N >> C;

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

	sort(house, house + N);

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

	while (start <= end)
	{
		int mid = (start + end) / 2;
		int prev = house[0];
		int set = 1;

		for (int i = 1; i < N; i++)
		{
			if (house[i] - prev >= mid)
			{
				set++;
				prev = house[i];
			}
		}

		if (set >= C)
		{
			ans = max(ans, mid);
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}

	cout << ans;
}