[c++] codeground 연습문제 '버스 타기'(2018년도 SCPC 예선1차)

문제 : www.codeground.org/practice/practiceProblemViewNew

 

 

처음은 큐를 이용하여 문제를 해결하려 하였다. (이는 시간초과가 발생하였다.)

 

 

1. 선수들의 실력을 오름차순으로 정렬하여 순서대로 큐에 넣는다.

 

2. 큐가 비워질 때 까지 순회하며, 현재 가장 작은 수 부터 시작해서, k 초과로 차이나는 선수들을 하나의 버스에 태운다.

 

 

 

예를들어 k=3이고, 실력이 1, 5, 3, 7, 9인 선수들을 태운다고 하면

이러한 방법으로 버스 두대로 나누어 태울 수 있다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int Answer;
unsigned int k;

int main(int argc, char** argv)
{
    int T, test_case,n;
    queue<unsigned int> q;

    cin >> T;
    
    for(test_case = 0; test_case  < T; test_case++)
    {

        Answer = 0;
        
        unsigned int level[200001];
        scanf("%d %d",&n,&k);
        
        for(int j=0 ; j< n ; j++){
            scanf("%d",&level[j]);
        }
        sort(level, level + n);
        
        for(int j=0 ; j< n ; j++){
            q.push(level[j]);
        }
        
        
        while(!q.empty()){
            unsigned int now_top = q.front();
            q.pop();
            int size = q.size();
            
            for(int i=0 ; i< size ; i++){
                unsigned int tmp = q.front();
                if(tmp - now_top > k){
                    now_top = tmp;
                    q.pop();
                }
                else{
                    q.pop();
                    q.push(tmp);
                }
            }
            Answer++;
        }
        
        
        cout << "Case #" << test_case+1 << endl;
        cout << Answer << endl;
    }

    return 0;
}

하지만 위에서도 언급했듯, 이 방법을 시간초과가 발생하였다.

 

 

 

 

 

 

시간초과가 발생하지않게 하기 위해서, 순차적으로 처리하는 방법을 선택하였다.

 

 

1. 선수들의 실력을 오름차순으로 정렬한다. 

 

2. 현재 타야 할 선수의 실력이 L이고, 현재까지의 버스 수가 i라면 (L-1) 선수부터 (L-i+1)선수 까지는 현재 버스에 나누어서 탈 수 있다.

    (L-i)번째 선수와 L번째 선수의 실력 차이가 k보다 작거나 같다면 두 선수를 같은 버스에 태울 수 없으므로 한대의 버스가 더 필요하다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int Answer;
unsigned int k;

int main(int argc, char** argv)
{
    int T, test_case,n;

    cin >> T;
    
    for(test_case = 0; test_case  < T; test_case++)
    {

        Answer = 0;
        
        unsigned int level[200001];
        scanf("%d %d",&n,&k);
        
        for(int j=0 ; j< n ; j++){
            scanf("%d",&level[j]);
        }
        sort(level, level + n);
        
        for(int j=0 ; j< n ; j++){
            if(level[j] - level[j-Answer] <= k) Answer++;
            
        }
        
        
        cout << "Case #" << test_case+1 << endl;
        cout << Answer << endl;
    }

    return 0;
}