백준 1946 신입 사원

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

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

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;

    cin >> t;

    for (int test = 0; test < t; test++) {
        int n;
        vector<pair<int, int>> arr;

        cin >> n;
        arr.resize(n);

        for (int i = 0; i < n; i++) {
            cin >> arr[i].first >> arr[i].second;
        }

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

        int temp = 0;
        int ans = 1;

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

    }

    return 0;
}

1. 문제

n명의 회사 지원자의 서류 심사 성적 순위와 면접 심사 성적 순위가 주어진다. 회사가 두 성적 중 하나라도 다른 지원자보다 떨어지지 않는 자를 선별한다고 할 때, 선별할 신입의 최대 인원 수를 구하라.

2. 풀이

우선 서류 심사로 뽑을 수 있는 사람을 먼저 뽑고, 그 후 면접 심사 성적을 비교하기로 하자.

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

서류 심사 성적 순으로 정렬한다. 순위로 주어지므로 오름차순으로 정렬한다.

        int temp = 0;
        int ans = 1;

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

우선 서류 심사 1등은 다른 사람보다 서류 심사 점수가 뛰어나다는 뜻이므로 뽑는다. 그 후 반복문을 돌면서 반복문 인덱스에 해당하는 면접자는 앞에서 뽑힌 사람보다 서류 심사 점수가 떨어지므로 면접 심사 점수가 높아야 뽑힐 수 있다. 따라서 면접 심사 점수를 비교하여 더 높으면 해당 인원을 뽑는다.

이 결과 나오는 사람 수 ans를 출력하면 정답을 구할 수 있다.