SCPC 2018 1차 예선: 버스타기 (C++)

문제 설명

-n명의 선수들의 실력이 입력으로 주어진다.

 

-실력차이가 k이하인 선수들은 같은 버스에 타고 있을 수 없다.

 

-이 때 필요한 버스의 수는?

 

 

풀이

처음에는 벡터에 pair을 담는 형태로 선수 정보와 버스 정보를 담으려고 했다.

 

이 방식으로 하면 새로운 선수에 대한 처리를 할 때마다, 이전의 선수들에 대한 정보를 모두 검사해야 한다.

 

하지만 n < 200,000이기 때문에 O(N) 못해도 O(nlogn)에는 해결하겠다는 생각으로 접근해야 할 것이다.

 

기본 아이디어는 선수들의 실력을 오름차순으로 정렬하는 것이다.

 

정렬된 배열 1 3 4 5 7 9 를 선수 정보라고 치고, k = 3이라고 한다면

 

3은 1과 같은 버스에 탈 수 없다. (3 - 1 < k ) 3까지 확인한 결과로 버스는 두대가 필요하다.

 

4를 확인할 때, 이미 두대가 필요한 것을 알고 있으므로 두칸 앞으로가서 1부터 비교한다. 1과도 같은 버스에 탈 수 없기 때문에 버스는 한대가 더 추가된다. 1과도 같이 탈 수 없으면, 정렬된 상태이기 때문에 1보다 더 큰 실력을 가진 사람과는 비교할 필요도 없는 것이다.

 

5를 확인할 때 이미 세대가 필요하다는 것을 알고있으므로 세칸 앞으로 가서 1부터 확인한다. 1과 5는 같은 버스에 탈 수 있다.

 

이런식으로 진행해주면 된다.

 

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

int arr[200001];
int main(void) {

	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {

		int n, k;
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		sort(arr, arr + n); //오름차순 정렬
		
		int bus = 1;

		for (int i = 1; i < n; i++) {
			if (arr[i] - arr[i - bus] <= k)
				bus++;
		}
		cout << "Case #" << t << '\n' << bus << '\n';
	}
	return 0;
}