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

문제 링크

1946번: 신입 사원

 

풀이

그리디 문제. n이 10^5라서 완탐으로 풀기엔 시간 초과가 남

1. a와 b를 입력 받으면서 a의 등수 인덱스에 b의 등수를 넣는다.
2. 1등은 무조건 합격이기에, minNum을 1등의 b 점수로 넣고 2등부터 확인한다.
3. minNum보다 arr[i]가 크다는 것은, 나보다 a 점수가 좋은 사람들이 b 점수도 좋다는 뜻이므로 제외한다.
4. minNum은 계속해서 최솟값으로 갱신한다.

예제를 통해 arr를 만들면 이런 식이 될 것이다.

a 등수 인덱스	1 (등)	2	3	4	5	6	7
arr (b 등수)	4 (등)	5	6	2	7	1	3

 

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t-- > 0)
    {
        int n;
        cin >> n;
        vector<int> arr(n + 1);

        int tmp1, tmp2;
        for (int i = 0; i < n; i++)
        {
            cin >> tmp1 >> tmp2;
            arr[tmp1] = tmp2;
        }

        // 1등은 무조건 합격, 기준은 1등의 b 점수부터
        int minNum = arr[1];
        int answer = n;
        for (int i = 2; i <= n; i++) 
        {
            if (minNum < arr[i])
            {
                answer--;
            }
            minNum = min(minNum, arr[i]);
        }
        cout << answer << '\n';
    }
}