[백준/2110] 공유기 설치

1. 문제

1) 문제 링크

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

2110번: 공유기 설치

 

2) 설명

수평선 위에 N개의 집이 있고 N개의 집에 C개의 공유기를 설치하는 문제.

문제에서 말하는 "가장 인접한 두 공유기 사이의 거리를 최대로 하는" 이 조금 이해하기 힘들었지만 결국

공유기가 설치된 집들 간의 거리의 최소값을 최대로 만들면 된다.(말이 조금 어렵다)

예를 들어

index	0	1	2	3	4	5
위치	1	3	8	10	14	20
공유기 설치	O	X	X	O	X	O

위와 같은 상황이라면 답은 0번째 집, 3번째 집, 5번째 집에 설치를 해서 공유기가 설치된 이웃집 간 최소 거리의 최대값인 9 ( maximize( min( dist(house[0], house[3]), dist(house[3], house[5]) ) ) ) 이 된다.

 

2. 풀이

1) 알고리즘

    : 이분탐색

 

2) 풀이 설명

 공유기가 설치된 이웃집 거리는 1에서 (수평선에서 가장 오른쪽 집과 가장 왼쪽 집 거리) 범위 안에 있을 수 있다.

그래서 그 거리를 구하기 위해 + 이분 탐색을 위해 houses(집 위치 벡터)를 정렬해준다.

이후 이분탐색을 통해서 최소 거리의 최대값을 찾아나간다.

이때 getMinDist 함수를 통해서 인자로 입력받은 거리 이상으로 공유기 설치가 가능한지 판단하고 불가능하다면 -1을, 가능하다면 그때의 거리 최소값(인자로 입력받은 거리 이상의)을 리턴해주도록한다.

 

getMinDist 함수에서 첫 번째 집(가장 왼쪽)은 반드시 공유기를 설치한다고 가정한다. 그 이유는 다음과 같다.

처음 공유기가 설치되는 집이 x번째 ( x > 1 )라고 해보자. 그러면 x번쨰 집(hosues[x])과 그 다음 공유기가 설치된 집(houses[x + n]) 간의 거리는

1. 공유기가 설치된 집 중 가장 가까운 거리

2. 공유기가 설치된 집 중 가장 가깝지는 않은 거리

중 하나다.

당연한 말 같아보이지만 첫 번째 집에 공유기를 설치해야되는 이유를 설명하는 데 이 두 가지 경우를 나눠서 생각하는 게 필요하다고 생각한다.

이제 x번째 집에서 공유기를 제거하고 첫 번째 집(houses[0])에 공유기를 설치한다고 생각해보자.

그러면 그 다음 공유기가 설치된 집(houses[x + n])과 첫 번째 공유기가 설치된 집(이제는 houses[0]) 사이의 거리는 공유기를 x번째에 설치했을 때보다 멀어질 것이다.

그러면 위의 1번의 경우에는 공유기가 설치된 집 간 거리 중 최소값이 증가하게 된 것이니까 답을 잘못 구한 게 된다.(더 큰 최소값을 찾을 수 있다는 말)

그리고 2번의 경우에는 이 첫 번째 공유기가 설치된 집과 두 번째 공유기가 설치된 집 사이의 거리가 늘어나도 어차피 최소 거리보다는 크기 때문에 전혀 상관이 없다.

결론적으로 문제에서 요구하는 "가장 인접한 두 공유기 사이의 거리를 최대로 하는 집들"을 선택했을 때 그 시작이 첫 번째(houses[0])집이 아니라면 1번의 경우에는 더 큰 최소값이 있으므로 답을 잘못 구한 게 되고 2번의 경우에는 첫 번째 집을 고르든 말든 전혀 상관이 없다는 말이다. 즉 첫 번째 집에 무조건 공유기를 설치했다고 가정하는 것은 답을 구하는 데 충분조건으로 작용한다는 말이다.

이 논리는 반대로 마지막 집에도 똑같이 적용된다.

 

또한 사실 getMinDist 함수를 인자로 받은 거리로 공유기 설치가 가능한지만 판단해줘도 되는데 모든 집 사이의 거리가 넓은 경우에 시간을 더 단축할 수 있지 않을까 해서 인자로 받은 거리 이상의 거리(즉 공유기가 설치된 집 간의 거리가 인자로 받은 거리 이상으로 위치하게 하는 실제 거리)를 리턴하도록 해주었다. (근데 속도를 보니 크게 시간 단축의 효과는 없는 것 같았다ㅠㅠ)

 

3. 코드

 

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

using namespace std;

typedef long long LL;

const LL MAX_VAL = 999999999;
LL N, C;
vector<LL> houses;

LL getMinDist(LL minDist){
	LL answer = MAX_VAL;
	int prevHouse = 0; // 이전 집과의 거리를 구하기 위해 이전 집의 index를 저장해놓을 변수
	LL numOfAP = 1; // 설치된 공유기의 개수. 첫 집에 설치된 상태에서 시작하기 때문에 초기값 1

	for(int i=1;i<houses.size() && numOfAP<=C;i++){
		if(houses[i] - houses[prevHouse] >= minDist){
        	//집 간 거리가 인자로 받은 최소거리보다 크다면 업데이트
			answer = min(answer, houses[i] - houses[prevHouse]); // 거리 업데이트
			prevHouse = i; // 이전 집 index 업데이트
			numOfAP++; // 설치된 공유기 개수 증가
		}
	}

	if(numOfAP < C){
		//공유기를 적게 놓았으면 -1 return
		return -1;
	} else {
		return answer;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	LL input, answer = 0;
	cin >> N >> C;
	
	houses.reserve(N);
	for(int i=0;i<N;i++){
		cin >> input;
		houses.push_back(input);
	}
	
	//sort
	sort(houses.begin(), houses.end());
	
	//binary search
	LL s = 0;
	LL e = houses.back() - houses.front();
	while(s<=e){
		LL mid = (s + e)/2;
		LL minDist = getMinDist(mid);//mid 이상의 거리의 최소값을 구함

		if(minDist >= mid){
			s = minDist + 1;
			answer = max(answer, minDist);// 최소 거리의 최대값을 구해야 하므로 minDist >= mid 일 때만 업데이트
		} else {
			e = mid - 1;
		}
	}
	
	cout << answer << endl;

	return 0;
}

 

 

4. 느낀점

이분탐색은 자주 구현해도 어려운 것 같다...