scpc Practice 버스타기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int Answer;
int n;
int k;
int main(int argc, char** argv)
{
    int T, test_case;
 
 
 
    cin >> T;
    for (test_case = 0; test_case < T; test_case++)
    {
        cin >> n >> k;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        sort(arr.begin(), arr.end());
        Answer = 0;
        for (int pos = 0; pos < n; pos++) {
            if (arr[pos] - arr[pos - Answer] > k) {
                continue;
            }
            else {
                Answer++;
            }
        }
 
        cout << "Case #" << test_case + 1 << endl;
        cout << Answer << endl;
    }
 
    return 0;
}

출처:https://www.codeground.org/practice/practiceProblemViewNew

1.문제를 처음풀때 그냥 제일 최솟값을 구해서 현재 위치-최솟값>k이면 다 같은 버스를 태워야지 이런 식으로 문제를 풀었는데

생각 해보니 같은버스에 전부다 태우면 최솟값 제외한 친구들도 고려를 해줘야 해야되는걸 생각하지 못했습니다.

2.정렬시키고 각자 다 다른 버스에 태우기 위해 버스의 대수를 고려서 문제를 풀어 줬습니다. 

1 3 4 7 8 의 경우를 보면 7,8의 경우는 서로 다른 버스에 타야합니다. 

그 조건을 만족시키기위해서  arr[pos] - arr[pos - Answer] 라는 조건을 써줬습니다.

Answer는 현재보유하고있는 버스의 수를 의미합니다.

처음에 long long을 사용해서 문제를 풀었는데 숫자가 10억이니 int형을 사용해도 잘 풀리네요. 

int형은 약 20억이상이면 범위 오류가 난다고 합니다.