백준(BOJ)_신입사원(1946번)_C++

처음에 문제를 이해하는 것부터 쉽지 않았다.

그러다가 질문들에 있는 여러 테스트 케이스를 확인해보면서 문제를 이해했던 것 같다.

 

풀이 과정은 다음과 같다.

우선 입력받은 성적의 배열을 서류 성적 순위를 기준으로 오름차순으로 정렬한다.

그러면 이 배열의 0번째 인덱스는 무조건 신입사원에 선발될 것이다.

(왜냐하면 나머지 지원자들보다 서류 성적이 높기 때문이다. )

 

그리고 이 0번째 인덱스의 면접 성적을 기준으로 계속해서

이후 인덱스의 면접 성적을 비교한다.

이 때 i번째 인덱스의 서류 성적은 0번째보다 무조건 낮으므로,

0번째보다 면접 성적이 높은 i를 찾아서 신입사원으로 선발하면 된다.

 

0번째 다음으로 신입사원을 선발했으면 이 i번째 인덱스를 기준으로

계속해서 똑같이 면접 성적을 비교한다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, t;
pair<int, int> grd[100000]; //서류, 면접

bool comp(pair<int, int> a, pair<int, int> b){
    return a.first < b.first ? true : false;
}

void solve(){
    sort(grd, grd+n, comp);
    pair<int, int> temp=grd[0];
    int answer=1;

    for(int i=1; i<n; i++){
        if(temp.second > grd[i].second){
            answer++;
            temp=grd[i];
        }
    }
    cout << answer << "\n";
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> t;
    while(t--){
        for(int i=0; i<100000; i++){
            grd[i]={0, 0};
        }

        cin >> n;
        for(int i=0; i<n; i++){
            int a, b;
            cin >> a >> b;
            grd[i]={a, b};
        }
        solve();
    }
}