[BOJ 1946] 신입사원

이 문제는 브루트포스로 비교하게 되면, 시간 초과가 발생한다.

 

 

 

그리고, 이 문제의 분류도 그리디 알고리즘이므로 더더욱 브루트포스는 아닐 것이다.

 

 

 

문제에서 원하는 것은, 

 

 

 

"그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다."

 

 

 

 

을 만족하는, 신입사원의 수이다.

 

 

 

서류심사를 기준으로 지원자들을 정렬하면, 특정 지원자가 합격하기 위해서는, 자기의 서류심사점수보다 높은 지원자들을 대상으로 면접 시험 성적이 높아야 한다.

 

 

 

정렬을 하고, 브루트 포스로 비교를 하면 시간초과가 발생한다.

 

 

 

서류심사를 기준으로 정렬된 지원자들을 순차적으로 평가해야할 때, 가장 최근에 뽑힌 지원자의 면접시험 성적보다 좋으면 합격할 수 있다.

 

 

 

최근에 뽑힌 지원자의 면접시험의 성적보다만 좋으면 되는 것이, 그리디 알고리즘의 의미를 담고 있다.

 

 

 

위의 부문을 이해하고 코드를 작성하면 된다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int T;
int N;
int val1, val2;
int answer = 0;
 
int main() {
    cin >> T;
    for(int i = 1; i <=  T; i++){
        cin >> N;
        vector<pair<int, int>> v;
    
        for(int j = 1; j <= N; j++){
            cin >> val1 >> val2;
            v.push_back(make_pair(val1, val2));    
        }
        sort(v.begin(), v.end());
        int temp = v[0].second;
        answer = 1;
        
        for(int j = 1; j < v.size(); j++){
            if(v[j].second < temp){
                answer += 1;
                temp = v[j].second;
            }
        }
        
        cout << answer << endl;
    }
    
    return 0;
}