백준 공유기설치

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

 

 

백준 공유기설치 문제이다.
이진탐색 문제인데 꽤나 신박한 문제였다.
문제를 본 순간 드는 생각은 공유기를 하나하나씩 둬 보면서 경우의 수를 따져보는 것이었다. 다시 말해서 완전탐색으로 풀 수 있는 문제지만 역시 백준문제답게 시간제한이 있으므로 완전탐색보다 빠른 이진탐색을 이용하면 풀 수 있을거라 생각했다.

공유기설치하는 집 사이의 최소거리를 이진탐색으로 찾는것을 생각하는 것이 꽤나 어려웠다.

 

 

해결 알고리즘

1. 이진탐색으로 nCurDst를 설정한다.

2. 설정한 nCurDst로 공유기를 다 설치할 수 있는지 확인한다. (CheckDistance())

3. 공유기를 설치할 수 있으면 더 큰 nCurDst로 다시 탐색하고 해당 nCurDst를 저장한다.

   3-1. 공유기를 설치할 수 없으면 더 작은 nCurDst로 다시 탐색한다.

4. 종료조건은 더 이상 탐색할 nCurDst가 없을때 종료한다.

 

소스코드는 다음과 같다.

   #include <iostream>
#include <algorithm>
#include <assert.h>

using namespace std;

// brief : 현재 nCurDst로 공유기 설치가 가능한지 검사.
//input : 집의 위치정보배열, 탐색해볼 distance, 집 개수, 공유기 개수
bool CheckDistance(int home[], int dist, int N, int M)
{
	int visit = 0;
	M--;	// 첫 번째 집에 공유기 설치.

	for (int i = 1; i < N; i++)
	{
		if (M > 0)	// 아직 설치할 공유기가 남아있는 경우
		{
			if (home[i] - home[visit] >= dist)
			{
				visit = i;
				M--;
			}
		}
		else // M == 0, 해당 dist로 공유기 전체설치 성공. dist 더 큰경우를 탐색해보자.
		{
			return true;
		}
	}

	if (M > 0)	// dist 줄여야함.
	{
		return false;
	}
	else if (M == 0)	//해당 dist로 성공. dist 더 큰경우를 탐색해보자.
	{
		return true;
	}
	else 
	{
		// none
	}
}

int main()
{
	int N, M;
	int home[200000];
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> home[i];	// 집 입력받기(배열)	
	}

	//sorting 한번 해야돼
	sort(home, home + N);

	int dst_save = 1;	//답
	int nMaxDst = (home[N - 1] - home[0]) / (M - 1);
	int nMinDst = 1;
	int nCurDst = 1;

	while (nMinDst <= nMaxDst)
	{
		nCurDst = (nMaxDst + nMinDst) / 2;

		if (CheckDistance(home, nCurDst, N, M))	// 공유기 설치 성공한 경우. 더 큰경우 탐색
		{
			if (nCurDst == nMaxDst)
			{
				cout << nCurDst;
				break;
			}
			dst_save = nCurDst;
			nMinDst = nCurDst + 1;

			
		}
		else // 설치가 안되면 작은 케이스를 탐색해야하거나 or 종료조건인 경우다.
		{
			if (nMinDst == nMaxDst) // 종료조건
			{
				cout << dst_save;
				break;
			}
			else //left side search
			{
				nMaxDst = (nCurDst == nMinDst ? nCurDst : nCurDst - 1);
			}
		}
	}

	return 0;
}