[BOJ 20917 // C++] 사회적 거리 두기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 20917번 문제인 사회적 거리 두기이다.
문제는 아래 링크를 확인하자.

https://www.acmcipc.net/problem/20917

 

모든 두 좌석 사이의 거리가 \(K\) 이상이 되도록 자리를 고를 때 고를 수 있는 최대 자리 수를 구하는 것은 좌석을 한쪽 끝부터 그리디하게 고르는 전략으로 어렵지 않게 구할 수 있다. 그리고 \(K\)의 값이 커지면 고를 수 있는 자리의 수는 같거나 적어지고, \(K\)의 값이 작아지면 고를 수 있는 자리의 수는 같거나 커진다는 성질을 관찰할 수 있다..

 

위의 관찰을 이용하면 고를 수 있는 자리의 수가 \(S\) 이상이 되게끔 하는 거리 \(D\)의 범위를 이분탐색을 통해 구할 수 있다. 이를 이용해 문제를 해결하자.

 

\(X\)값을 활용하기 전 먼저 정렬을 해야 함에 유의해 구현하자.

 

아래는 제출한 소스코드이다.

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

int N, S;
int A[200000];
void solve() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);

	int L = 1, R = 999999999;
	while (L < R) {
		int cnt = 0, old = -1000000007;
		int mid = (L + R) / 2 + 1;
		for (int i = 0; i < N; i++) {
			if (A[i] - old >= mid) cnt++, old = A[i];
		}
		if (cnt >= S) L = mid;
		else R = mid - 1;
	}
	cout << L << '\n';
}

int T;

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

	cin >> T;
	while(T--) solve();
}