백준 2110 c++ "공유기 설치" -PlusUltraCode-

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

 

[필자 사고]

이분탐색이라고 생각하는 사고 과정이 어려운 문제였다.

이분 탐색이라고 깨달아도 어떻게 해야 제일 작은 거리가 최대이게 할 수 있을지도 고민을 좀 해야 되는 문제였다.

약간 이분탐색은 정해진 해결법이 있다고 생각한다.

일단 배열이 정렬되어 있어야 하고

어떠한 범위내 값을 찾을때?? 이러면 이분탐색을 의심해 볼만하다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. Input

• 기능: 집의 개수 N과 설치할 공유기 개수 M을 입력받고, 이어서 집의 좌표를 입력받는다. 입력받은 좌표들을 정렬하여 탐색을 위한 준비를 마친다.

---

2. isOk

• 기능: 매개변수로 주어진 거리 mid를 기준으로, 공유기를 M개 이상 설치할 수 있는지를 판단한다. 첫 번째 집에는 항상 설치하고, 이후의 집들과의 거리를 확인해 조건을 만족할 때마다 공유기를 설치하며 개수를 센다. 최종적으로 설치한 개수가 M 이상이면 설치가 가능하다고 판단한다.

---

3. Game_Start

• 기능: 가장 인접한 두 공유기 사이의 거리를 최대화하는 문제를 해결하기 위해 이분 탐색을 수행한다. 가능한 거리의 범위를 start부터 end까지 설정한 후, 중간 거리 mid를 기준으로 공유기 설치 가능 여부를 판단한다. 설치 가능하면 거리의 하한을 늘리고, 불가능하면 줄이면서 최적의 값을 찾아낸다. 최종적으로 가능한 최대 거리를 출력한다.

[소스 코드]

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

int N, M;
vector<int> arr;

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());
}

bool isOk(int mid) {

	int count = 1;
	int last = arr[0];
	for (int i = 1; i < N; i++) {
		if (arr[i] - last >= mid) {
			count++;
			last = arr[i];
		}
	}
	return count >= M;
}

void Game_Start() {
	int start = 1;
	int end = arr[N - 1] - arr[0];
	int dist = 0;
	while (start <= end) {
		int mid = (start + end) / 2;

		if (isOk(mid)) {
			start = mid + 1;
			dist = mid;
		}
		else {
			end = mid - 1;

		}
	}

	cout << dist;
}

int main(void) {
	Input();
	Game_Start();
}