[백준 2110번 C/C++] 공유기 설치

 

[백준 2110번 C/C++] 공유기 설치

 

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

2110번: 공유기 설치

---

 

 

해결방안

 

이분 탐색 

매개 변수 탐색

 

---

 

코드

 

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

int n, c;
vector<int> v;

bool isValid(int distance)
{
	int cnt = 1;
	int lastInstalled = v[0];
    
	for (int i = 1; i < n; i++)
	{
		if (v[i] - lastInstalled >= distance)
		{
			cnt++;
			lastInstalled = v[i];
		}
	}

	return cnt >= c;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);

	cin >> n >> c;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	
	sort(v.begin(), v.end());//집 오름차순 정렬

	//이분 탐색 초기값 설정.
	int left = 1;
	int right = v[n - 1] - v[0];
	int result = 0;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (isValid(mid))
		{
			result = mid;
			left = mid + 1;
		}
		else
		{	
			right = mid - 1;
		}
	}

	cout << result;


	return 0;
}

 

 

---

 

코드 해설 - 주석

 

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

int n, c;
vector<int> v;

//주어진 거리(distance)가 가능한지 판별하는 함수
bool isValid(int distance)
{
	int cnt = 1;//공유기를 설치한 집의 개수. 초기값을 1로 설정.
	int lastInstalled = v[0];//공유기를 설치한 집의 위치. 초기값을 v[0]로 설정.

	//두 번째 집부터 마지막 집까지 순회.
	//각 집의 위치와 마지막으로 설치된 공유기와의 거리 차이가 distance 이상이면 공유기를 설치할 수 있다.
	//해당 경우, 공유기를 설치한 집의 개수를 나타내는 cnt를 증가시키고, 마지막으로 설치된 공유기의 위치를 현재 집으로 갱신한다.
	for (int i = 1; i < n; i++)
	{
		if (v[i] - lastInstalled >= distance)
		{
			cnt++;
			lastInstalled = v[i];
		}
	}

	//공유기가 설치된 집의 개수가 c개 이상이라면 distance는 가능한 거리 값이다.
	return cnt >= c;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);

	cin >> n >> c;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	
	sort(v.begin(), v.end());//집 오름차순 정렬

	//  1        2       4        8        9
	//v[0],    v[1],    v[2],    v[3],    v[4]
	//	    1        2       4         1


	//이분 탐색 초기값 설정.
	int left = 1;//공유기 사이 최소 거리(=집 사이 최소 거리)
	int right = v[n - 1] - v[0];//공유기 사이 최대 거리(=집 사이 최대 거리)
	int result = 0;//c개의 공유기를 설치했을때 두 공유기의 최대 거리

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (isValid(mid))//mid값이 유효하다면
		{
			result = mid;//두 공유기의 최대 거리는 mid로 설정.
			left = mid + 1;//현재 설정한 최대 거리보다 더 큰 거리를 찾기 위해 left를 mid+1로 변경한 후 다시 이분탐색(while문을 돌린다).
		}

		//mid가 유효한 거리값이 아닌 경우, mid값보다 작은 값을 찾기 위해
		//right을 mid-1로 변경한 후 다시 이분탐색(while문을 돌린다).
		else
		{	
			right = mid - 1;
		}
	}

	cout << result;


	return 0;
}

 

 

 

 

 

---