[C++]백준 - 2110번 문제

2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

 

2110번 : 공유기 설치

---

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

 

출력

---

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

 

---

 

생각해 볼 점

---

가장 인접한 공유기 사이의 거리의 최댓값이므로 매개변수 탐색 방법으로 풀 수 있습니다.

 

이분 탐색이므로, left와 right를 설정합니다.

 

left = 0, right = 가장 먼 집 사이의 거리 + 1로 두겠습니다.

 

이분 탐색법을 이용하여 mid = (left + right) / 2이고,

우리는 이 mid 값을 정답이라고 가정합니다.

 

가장 인접한 공유기 사이의 거리이므로, 다른 공유기 사이와의 거리는 mid보다 커도 됩니다.

 

예를 들어, mid = 3이고, 집 사이의 거리가 다음과 같다면,

 

A - 3 - B - 5 - C

 

A, B, C 세 곳에 모두 공유기를 설치해도 무방합니다.

 

반면, 3이 정답이라 가정했을 때, 집 사이의 거리가 다음과 같다면,

 

A - 1 - B - 4 - C

 

A와 B 사이에는 공유기를 설치할 수 없음이 자명합니다. 따라서, A에서 B 집을 건너뛰고 C에 공유기를 설치하여 거리를 3 이상으로 유지해야 합니다. 3을 정답이라 가정했을 때, 3보다 짧은 거리는 있을 수 없기 때문입니다.

 

이런 방법으로 집 사이의 거리가 mid값 이상일 때마다 공유기를 하나 설치하여 공유기의 갯수가 입력 값과 같을 경우를 찾습니다. 이런 경우 중 mid값이 가장 작은 경우가 정답이 됩니다.

 

 

 

코드

---

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

int main() 
{
	int N, C;
	cin >> N >> C;
	
	vector<int> house;		//집의 위치
	for(int i = 0; i < N; i++) 
	{
	    int input;
	    cin >> input;
	    house.push_back(input);
	}
	
	sort(house.begin(), house.end());
	
	int left = 0, right = house[N - 1] - house[0] + 1;	//이분 탐색 준비
	while(left + 1 < right)
	{
	    int mid = (left + right) / 2;	//이 때, mid를 가장 인접한 공유기 거리로 가정
	    int count = 1;
	    int prev = house[0];
	    for(int i = 1; i < N; i++)
	    {
        	//mid보다 거리가 커질 때마다 공유기를 하나 설치함, count 증가
	        if(mid <= house[i] - prev)
	        {
	            count++;
	            prev = house[i];
	        }
	    }
	    
        //공유기의 갯수가 입력값보다 적으면 mid값을 줄임
	    if(count < C) right = mid;
	    else left = mid;
	}
	cout << left;
	return 0;
}

 

그 외

---