[백준][C++] 1946: 신입 사원

문제

1946번: 신입 사원

풀이

그리디, 정렬

 

먼저 서류심사 성적을 기준으로 정렬한다. 서류 성적 1등부터 7등을 0번부터 6등이라고 하자.

서류	면접
1	4
2	5
3	6
4	2
5	7
6	1
7	3

1. 0번은 서류 성적이 1등 이므로, 면접 성적이 낮아도 서류 성적이 제일 높기 때문에 무조건 선발된다.
2. 1번은 0번보다 서류 성적은 낮지만, 면접 성적이 높을 수 있다. 1번이 0번보다 면접 성적이 높다면 설발된다. 
3. 1번이 선발되었다고 가정하자. 마찬가지로, 2번은 1번보다 서류 성적은 낮지만 면접 성적이 높을 수 있다. 2번이 1번보다 면접 성적이 높다면 선발된다. 
4. 이를 반복한다. 

위의 방법을 토대로, 한 명이 선발되면 그 사람의 면접 성적이 다음 사람의 면접 성적 커트라인이 되며, 이 성적보다 낮다면 탈락된다. 

 

코드

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

using namespace std;

vector<pair<int, int>> nums;

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

    int T;
    cin >> T;

    while (T--)
    {
        int N;
        cin >> N;

        for (int i = 0; i < N; ++i)
        {
            int A, B;
            cin >> A >> B;
            nums.push_back(make_pair(A, B));
        }

        sort(nums.begin(), nums.end());

        // 0번은 서류심사 성적이 제일 높기 때문에, 무조건 선발된다. 
        // 1번은 0번보다 서류심사 성적은 낮지만, 면접 성적이 높을 수 있다. 
        // 1번이 0번보다 면접 성적이 높다면, 선발된다. 
        // 2번은 1번보다 서류심사 성적은 낮미나, 면접 성적이 높을 수 있다. 
        // 면접 성적의 커트라인을 0번의 면접 성적에서 1번의 면접 성적으로 변경한다. 
        // 반복
        int maxi = nums[0].second;
        int current = 1;
        for (int i = 1; i < N; ++i)
        {
            if (maxi > nums[i].second)
            {
                maxi = nums[i].second;
                current++;
            }
        }

        cout << current << '\n';

        nums.clear();
    }

    return 0;
}