BOJ - 1946 신입 사원

1946번 신입사원

회사에서 서류심사와 면접심사를 통해 신입사원을 선발한다.
선발하는 과정에서 만약 서류심사 결과와 면접심사 결과가 모두 다른 어느 지원자 보다 떨어진다면 그 지원자는 뽑힐수가 없다고 한다.

위의 조건을 통해 뽑힌 신입사원의 최대 인원수를 구하는 문제이다.

문제해결을 위한 순서는 다음과 같다.

1. 서류심사 등수와 면접심사 등수를 쌍으로 입력 받는다.
2. 서류심사 등수를 기준으로 오름차순으로 정렬한다.
3. 면접심사 등수를 기반으로 탐색한다.

pair를 통해 서류심사 등수와 면접심사 등수를 쌍으로 입력 받았기 때문에 서류심사 등수를 기준으로 정렬을 하게 되면 서류심사에 대한 비교는 이미 끝난 상태이다.

따라서 면접심사 등수만 비교하면 되는데, 예를들어 서류심사 정렬 결과 2등과 3등의 면접심사 등수를 비교하여 만약 3등의 면접심사 등수가 2등의 면접심사 등수보다 높다면 선발이 되는 것이고, 낮다면 선발이 안되는 것이다.

사용된 알고리즘으로는 정렬과 그리디 알고리즘을 사용하였다.

코드

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

using namespace std;

void sol()
{
    int n;
    cin >> n;

    vector<pair<int, int>> v;

    for(int i=0;i<n;i++)
    {
        int s,m;
        cin >> s >> m;
        v.push_back(make_pair(s,m));
    }

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

    int tmp = v[0].second;
    int cnt = 1;
    for(int i=1;i<n;i++)
    {
        if(v[i].second > tmp)
            continue;
        cnt++;
        tmp = v[i].second;
    }

    cout << cnt << "\n";

    return;
}

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

    int T;
    cin >> T;
    for(int i=0;i<T;i++)
    {
        sol();
    }
    return 0;
}

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