[인프런 C++] 44. 마구간 정하기 (이진탐색 응용)

🍧 문제

N개의 마구간이 1차원 수직선상에 있습니다. 각 마구간은 X1, X2, X3 ... XN의 좌표를 가지며, 마구간간에 좌표가 중복되는 는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두  말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때, 가장 가까운 두 말의 거리가 최대가 되는 그 최댓값을 출력하는 프로그램을 작성하세요.

 

✨ 1트 (강의 풀이)

마굿간의 위치를 정렬해준다. 1 2 4 8 9

답의 범위 : 최솟값 ~ 최댓값 사이 👉 1 ~ 9

두 말의 거리가 최대가 되야 하기 때문에, 1 위치부터 넣어본다.

 

1. mid = (1+9) / 2 = 5 👉 답이 되는지 체크

• 1 위치에 말 배치, 2 위치에 말 배치 👉 서로 빼줘서 최소 간격이 5가 되는지 체크 👉 1이기 때문에 2에 말 배치 불가
• 1 위치에 말 고정, 4 위치에 말 배치 👉 4-1 < 5 👉 4 위치에 말 배치 불가
• 1 위치에 말 고정, 8 위치에 말 배치 👉 8-1 > 5 👉 8 위치에 말 배치 가능
• 8 위치에 말 고정, 9 위치에 말 배치 👉 9-8 < 5 👉 9 위치에 말 배치 불가
• 따라서, 총 2마리의 말만 배치 가능하므로, 5는 답이 될 수 없고, mid 기준 오른쪽 날리

2. mid = (1+4) / 2 = 2

• 1 위치에 말 고정, 2 위치에 말 배치 👉 2-1 < 2 👉 2 위치에 말 배치 불가
• 1 위치에 말 고정, 4 위치에 말 배치 👉 4-1 > 2 👉 4 위치에 말 배치 가능
• 계속하면, 총 3마리의 말 배치 가능하므로, 2는 답이 될 수 있다. 👉 3 이상부터 4 이하 거리로 확인

3. mid = (3+4) / 2 = 3 이런식으로 계산하면 된다.

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

int n;

int Count(int len, vector<int> b){
	int cnt = 1, pos= b[1];
	for(int i = 2; i <= n; ++i){
		if(b[i] - pos >= len){
			cnt++;
			pos = b[i];
		}
	}
	
	return cnt;
}

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	
	sort(a.begin(), a.end());
	
	int left = 1, right, mid, res;
	right = a[n];
	
	while(left <= right){
		mid = (left + right) / 2;
		if(Count(mid, a) >= m){
			res = mid;
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
	}
	
	cout << res;
	
	return 0;
}