[백준] 1946 신입 사원 c++

접근 

두 가지의 성적을 비교하여 신입 사원 간 우위를 확인하기 위해서는 서류 성적을 먼저 정렬할 필요가 있어 보입니다. 그 후 면접 성적을 비교하여 가장 많은 신입 사원의 수를 계산해야 합니다. 

정렬 후 첫 번째 신입사원은 다른 신입사원보다 반드시 서류 성적이 뛰어날 것이므로 면접 성적이 어떻게 되었든 반드시 합격하는 신입사원입니다. (정렬 후 그리디한 접근이 이 문제에서 반드시 최대의 경우의 수를 도출하는 이유입니다.) 

첫 번째 신입 사원과 두 번째 신입사원의 면접 성적과 비교하였을 때, 만약 첫 번째 신입사원보다 면접 성적이 좋은 경우 두 번째 신입사원을 비교 기준으로 변경합니다. 

달리 얘기해서, 이미 서류 성적이 낮은 세 번째 네 번째 ... 신입 사원들은 두 번째 신입사원보다 면접 성적이 높기만 하면 합격입니다. 

만약 첫 번째 신입사원보다 면접 성적이 낮을 경우 첫 번째 신입사원을 비교 기준으로 유지합니다. 

즉, 첫 번째 신입사원의 면접 성적과 세 번째 신입사원의 면접 성적과 비교합니다. 위 (그리디한) 탐색을 반복하여 합격 가능한 신입 사원 최대의 수를 도출할 수 있습니다.

 

솔루션 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T, N;

int main () {
    cin >> T;
    for(int t=0; t<T; t++){
        cin >> N;
        vector < pair<int, int> > V;
        // 입력
        for(int n=0; n<N; n++){
            int a, b;
            cin >> a >> b;
            V.push_back(make_pair(a, b));
        }

        // 계산 및 출력
        sort(V.begin(), V.end());
        int answer = 1;
        int cur = V[0].second;

        for(pair<int, int> P : V){
            if(cur == P.second){
                continue;
            }
            if(cur > P.second){
                cur = P.second;
                answer += 1;
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

 

참고 자료

https://www.acmicpc.net/problem/1946