[백준 20917번] 사회적 거리 두기 (C++)

문제링크 : https://www.acmicpc.net/problem/20917

20917번: 사회적 거리 두기

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

long long t, n, s, arr[200001];
int cnt = 0, result;

void binary_search(int l, int h)
{
	while (l <= h)
	{
		int mid = (l + h) / 2;
		cnt = 1;  //맨 처음 값은 항상 포함
		int num0 = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] - num0 >= mid)  //해당 차이값(거리)이 현재 값보다 클때
			{
				cnt++;
				num0 = arr[i];  //다음 값으로 옮김
			}
		}

		if (cnt >= s)  
		{
			result = mid;
			l = mid + 1;
		}
		else
		{
			h = mid - 1;
		}
	}
}

int main()
{
	fastio;
	cin >> t;

	while (t--)
	{
		cin >> n >> s;
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
		}
		sort(arr, arr + n);
		binary_search(1, arr[n-1] - arr[0]);  //최솟값과 최댓값
		cout << result << "\n";
	}

	return 0;
}

 

처음에 입력받은 배열을 정렬해주고, 탐색값으로 최솟값과 최댓값을 넣어준다.

이때 거리가 아무리 적어도 1보다 작아지지않고, 마지막값과 처음값의 차이보다 클 수가 없기에 해당값들을 넣어준다.

 

이후 탐색과정에서 맨 처음 값은 항상 포함되기에 카운트는 1로 초기화해준다.

반복문에서 맨 처음값과 해당 배열값의 차이가 mid보다 크다면 조건을 만족하는 경우이기 때문에 카운트를 증가시키고, 다음 값과 비교하기 위해 (맨 처음값과 해당 배열값의 차이) -> (현재 배열값과 해당 배열값의 차이)를 구하도록 바꿔준다.

 

이렇게 늘어난 카운트가 S(팀수)보다 크다면 해당 mid 값은 조건을 만족한것이기에 결과값에 담아준다.