🙇‍♀️마구간 정하기 (이분검색 응용)

N개의 마구간이 1차원 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ……, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.

각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.

둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩 주어집니다.

▣ 출력설명
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

▣ 입력예제 1 
5 3
1
2
8
4
9

▣ 출력예제 1
3

🚀풀이

43번 뮤직 비디오와 비슷한 풀이이다.

Count함수는 만약 최대 거리가 num이라면 말이 최소 num만큼 떨어져서 배치했을 때 가능하지 확인하는 함수이다.

배열은 정렬되어 있고, cnt라는 변수로 말의 수를 확인한다.
if (seq[i] - pos >= num)로 말과 말사이의 간격이 num이상 떨어졌는지 확인한다.

solve함수를 보면 결정알고리즘을 그대로 사용하는데, C라는 결과를 두고 나올 수 있는 모든 결과를 경우의 수로 둔다.
가능한 경우 중에서 가장 높은 값을 찾는 과정을 solve에서 한다.

int N, C, lt = 0, rt = 0, mid, res;
vector<int> seq;

int Count(int num, const vector<int> vec)
{
	int pos = vec[0], cnt = 1; // 0번째엔 첫 번째 말이 들어가므로 cnt는 1부터 시작한다.
	for (int i = 1; i < N; ++i) // 첫 번째 말이 들어갔으니 i는 1부터 순회한다.
	{
		if (seq[i] - pos >= num) // 말 사이의 간격이 num보다 크는지 확인
		{
			cnt++; // 말의 수 증가
			pos = seq[i]; // pos 갱신
		}
	}

	return cnt;
}

void solve()
{
	cin >> N >> C;
	seq = vector<int>(N);

	for (int i = 0; i < N; ++i)
		cin >> seq[i];

	sort(seq.begin(), seq.end());
	rt = seq[N - 1]; // N을 그대로 적으면 out of range

	while (lt <= rt)
	{
		mid = (lt + rt) / 2;
		if (Count(mid, seq) >= C)
		{
			res = mid;
			lt = mid + 1; // 최대가 되는 거리는 찾고 싶으니까 lt를 증가 시킨다.
		}
		else
		{
			rt = mid - 1;
		}
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// 이분탐색 응용

// N : 마구간의 개수
// C : 말의 수
int N, C, lt = 0, rt = 0, mid, res;
vector<int> seq;

int Count(int num, const vector<int> vec)
{
	int pos = vec[0], cnt = 1;
	for (int i = 1; i < N; ++i)
	{
		if (seq[i] - pos >= num)
		{
			cnt++;
			pos = seq[i];
		}
	}

	return cnt;
}

void solve()
{
	cin >> N >> C;
	seq = vector<int>(N);

	for (int i = 0; i < N; ++i)
		cin >> seq[i];

	sort(seq.begin(), seq.end());
	rt = seq[N - 1];

	while (lt <= rt)
	{
		mid = (lt + rt) / 2;
		if (Count(mid, seq) >= C)
		{
			res = mid;
			lt = mid + 1;
		}
		else
		{
			rt = mid - 1;
		}
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고