카테고리 없음

백준 1946번 - 신입 사원

셩님 2019. 6. 17. 02:39

백준 1946번 - 신입 사원

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

문제

  • 지원자의 서류심사 성적, 면접 성적의 순위가 주어짐
  • 서류심사의 성적이나 면접 성적이 적어도 다른 합격자들 보다 하나는 높아야 하는 경우, 나올 수 있는 최대 합격자의 수

입력

  • 테스트 케이스의 개수 T(1 ≤ T ≤ 20)
  • 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)
  • 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위
  • 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정

출력

  • 선발할 수 있는 신입사원의 최대 인원수

접근

  • 서류심사의 성적을 오름차순으로 정렬했을 때, 뒤의 지원자의 서류심사 성적은 무조건 앞의 지원자 보다 낮게 된다.

  • 이 때, 면접성적까지 앞의 지원자보다 낮게 된다면 합격자가 될 수 없으므로 패쓰!

  • 면접성적이 앞의 지원자들보다 좋다면 합격이고, 그 성적이 면접성적의 합격 기준이되며 반복

  • 예시)

    7
    3 6
    7 3
    4 2
    1 4
    5 7
    2 5
    6 1
    
    1. 서류심사를 오름차순대로 정렬
    1 4
    2 5
    3 6
    4 2
    5 7
    6 1
    7 3
    
    2. 면접성적을 차례대로 비교
    1 4 <- 다음에 올 사람은 면접성적이 4위보다 좋아야 함 (count : 1)
    2 5 <- Pass
    3 6 <- Pass
    4 2 <- 다음에 올 사람은 면접성적이 2위보다 좋아야 함 (count : 2)
    5 7 <- Pass
    6 1 <- 다음에 올 사람은 면접성적이 1위보다 좋아야 함 / 불가능 (count : 3)
    7 3 <- Break

C++ Code

#include <iostream>
#include <algorithm>
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        pair<int, int> p[100001];

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

        sort(p, p + n);

        int ans = 1;
        int temp = p[0].second;
        for (int i = 1; i < n; ++i) {
            if (p[i].second < temp) {
                ans++;
                temp = p[i].second;

                if (temp == 1) {
                    break;
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}