[백준] 1946번 신입 사원

[문제]

신입 사원을 뽑는데, 다른 모든 지원자와 비교했을 때

서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다.

이 조건을 만족시키면서 선발할 수 있는 최대 인원수는??

 

[풀이]

우선, 서류 성적을 기준으로 정렬을 하면, 어짜피 서류성적은 이미 정렬해놔서 고려할 필요가 없고 본인보다 서류 성적이 높은 사람들의 최고 면접 점수보다 본인의 면접 점수가 높으면 합격할 수 있습니다.

 

1

5

3 2  -> 1 4

1 4      2 3

4 1      3 2

2 3      4 1

5 5      5 5

예제를 바탕으로 위의 값(왼쪽)을 입력했다고 했을 경우,

1등은 다른 지원자보다 떨어질 수가 없기에 기준점으로 잡고자 우선 오름차순 정렬(오른쪽)을 해줍니다.

그 후, 면접성적이 본인보다 서류 성적이 높은 사람의 면접 성적(최대값)보다 높은 등수인지 확인합니다.

(면접 성적을 위에서부터 비교하며 max값을 갱신하고 그 값과 면접 성적을 비교합니다.)

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int t;
    cin >> t;
    while (t-- > 0) {
        int n;
        cin >> n;
        int cnt = 1;
        pair<int, int> p[100000];
        int a_idx, b_idx;
        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            p[i] = make_pair(a, b);
        }
        sort(p, p + n);
        int pivot = p[0].second;
        for (int i = 1; i < n; i++) {
            if (p[i].second < pivot) {
                cnt++;
                pivot = p[i].second;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

궁금한점, 지적할점 댓글 환영합니다:)