(C++) - 백준(BOJ) 1946번 : 신입 사원

www.acmicpc.net/problem/1946

1946번: 신입 사원

greedy문제였습니다.

 

풀이방법

 1. 매 테스트 케이스마다 n개의 서류심사, 면접심사 성적 순위를 pair로 한 data를 vector에 입력합니다. 

 

 2. 그 후 서류심사 성적 순위를 기준으로 오름차순으로 정렬합니다. 이렇게 되면 0번째 지원자를 제외한 나머지 인원들은 무조건 성적이 0번째보다 더 낮으므로 두번째 면접점수만 비교하면 됩니다. i번째 지원자의 면접성적이 i-1번째 지원자의 성적보다 순위가 높다면 적어도 한 가지는 이겼으므로 ans++해줍니다.  앞으로는 i번째 지원자의 면접성적보다 순위가 낮은 인원들은 뽑힐 수 없습니다. 따라서 합격 성적의 하한선을 계속 갱신해주면서 뽑히는지 여부를 따져줍니다.

 

 3. 정답을 출력합니다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using pii = pair<int,int>;

int t, n, ans;
vector <pii> v;

int main(){
    fastio;
    cin >> t;
    while(t--){
        cin >> n;
        v.resize(n);
        ans = 1;
        for(int i = 0; i < n; i++) 
            cin >> v[i].first >> v[i].second;
        sort(v.begin(),v.end());
        int minSecond = v[0].second;
        for(int i = 1; i < v.size(); i++)
            if(v[i].second < minSecond) 
                ans++, minSecond = v[i].second;
        cout << ans <<'\n';
    }
}