[PS] 백준 1946번: 신입 사원

|

문제

내가 이해한 문제 내용

서류점수의 순위와 면접점수의 순위가 주어질 때 지원자 A의 두 순위가 임의의 지원자 B의 두 순위보다 모두 낮을 경우에 해당 지원자는 탈락된다. 이 때 최대로 붙을 지원자의 수를 구하는 문제이다.

접근 방식

서류점수의 순위를 기준으로 오름차순 정렬하면 차례대로 볼 경우 항상 이전 지원자들의 순위보다 낮기 때문에 면접점수의 순위만 보고 판단해주면 된다. 면접점수의 순위는 이전 면접점수의 순위가 가장 높은 지원자의 것과 비교해야 한다. 왜? 항상 가장 높은 지원자의 서류점수 순위보다 낮기 때문에!! (여기서 순위가 높다는 것은 숫자는 작은 것을 의미)

어려웠던 점 & 배운 점

컴과사 수업 때 나왔던 문제 같은데, 딱히 어려운점은 없었다.

코드

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

typedef pair<int,int> pii;

int tc,n,doc,in,m,ans;
vector<pii> app;

int main(void)
{
    scanf("%d",&tc);
    while(tc--){
        ans = 1;
        scanf("%d",&n);
        for(int i=0; i<n; i++){
            scanf("%d%d",&doc,&in);
            app.push_back({doc,in});
        }
        sort(app.begin(),app.end());
        m = app[0].second;
        for(int i=1; i<n; i++){
            if(app[i].second<m){
                ans++;
                m = app[i].second;
            }
        }
        app.clear();
        printf("%d\n",ans);
    }
    return 0;
}