#727 (Div.2) C - Stable Groups

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

Problem tags : greedy, sortings

 

소팅을 활용한 그리디 알고리즘 문제이다.

 

문제에서 주어진 n, k, x 에 대해서 알아보자면,

 

n : the initial number of students

k : the number of students you can additionally invite

x : the maximum allowed level difference

 

주어진 Stable Groups를 문제에서 주어진 Examples를 통해 알아보려고 한다.

 

input

8 2 3

1 1 5 8 12 13 20 22 

 

이때 8명의 학생이 들어오고 최대 2명을 초대할 수 있으며 최대 간격은 3이라고 주어졌다.

 

그렇다면 초대할 수 없는 경우에 대해 학생들을 분리할 수 있는, 즉, Stable Groups 을 다음과 같이 형성할 수 있다.

 

[1, 1], [5, 8], [12, 13], [20, 22] => 총 4가지 (초대하지 않은 경우)

 

최대 1명을 초대할 수 있는 경우에는 다음과 같이 Stable Groups 을 형성할 수 있다.

 

[1, 1, 2, 5, 8], [12, 13], [20, 22] => 총 3가지 (1명 초대한 경우)

(이때 1에서 5의 간격은 4이고 최대 간격 3을 넘으며 1와 5사이에 최대 한명을 넣을 수 있다.)

 

최대 2명을 초대할 수 있는 경우에는 다음과 같이 Stable Groups 을 형성할 수 있다.

[1, 1, 2, 5, 8, 9, 12, 13], [20, 22] => 총 2가지 (2명 초대한 경우)

(이때 8에서 12의 간격은 4이고 최대 간격 3을 넘으며 8과 12사이에 최대 한명을 넣을 수 있다.)

 

만약 3명, 4명을 초대하는 경우에 Stable Groups 는 어떻게 형성될까?

 

최대 3명을 초대할 경우

[1, 1, 2, 5, 8, 9, 12, 13, 16], [20, 22] => 총 2가지 (3명 초대한 경우)

 

최대 4명을 초대할 경우

[1, 1, 2, 5, 8, 9, 12, 13, 16, 19, 20, 22] => 총 1가지 (4명 초대한 경우)

 

여기서 유심히 볼 것은 격차가 작으면서 동시에 Stable Group이 분리된 그 사이에 숫자를 넣음으로써 Stable Group의 수를 줄여나가는 것이 중요하다.

 

즉, 초기의 Stable Group의 총 갯수를 cnt라고 할 경우에, 초대할 수 있는 k 값과 Stable Group의 간격을 따져서 cnt 값을 줄여나가도록 한다.

 

Stable Group의 간격을 따져서 사람을 넣을 수 있는 수 (v[i] - v[i-1] - 1) / x 를 interval_V 벡터에다가 push 해주고 그 이후에 interval_V 벡터를 오름차순으로 정렬한다.

 

그 후에 초대할 수 있는 k값에 대하여 k - interval_V[i] >= 0 인 경우 총 갯수에서 1을 줄이고 해당 과정을 반복한다. (이때 0 미만인 경우 break)

 

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long n, k, x;
vector<long long> v;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> k >> x;
	for (int i = 0; i < n; i++) {
		long long a;
		cin >> a;
		v.push_back(a);
	}

	sort(v.begin(), v.end());

	int cnt = 1;
	vector<long long> interval_V;
	for (int i = 1; i < n; i++) {
		if (v[i] - v[i - 1] > x) {
			interval_V.push_back((v[i] - v[i - 1]-1) / x);
			cnt++;
		}
	}

	sort(interval_V.begin(), interval_V.end());

	if (interval_V.size() == 0) cout << 1;
	else {
		for (int i = 0; i < interval_V.size(); i++) {
			if (k - interval_V[i] >= 0) {
				k -= interval_V[i];
				cnt--;
			}
			else break;
		}
		cout << cnt;
	}

	return 0;
}