문제 요약

문제
다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가, 각 테스트 케이스의 첫째 줄에는 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 동석차는 없다.

풀이

풀이는 한 가지 아이디어로 요약된다.

어떤 성적에 대해서 나보다 성적이 높은 모든 사람에 대해서, 다른 성적은 그 사람 모두보다 높아야한다.

이 아이디어에 따르면 어떤 성적에 대해서 정렬했을 때, 다른 성적의 i번째 요소는 이전 요소들보다 좋아야만(작아야만) 통과할 수 있다.
왜냐하면 어떤 성적에 대해서 정렬을 하면, i번째는 i-1번째보다 못본 것이 보장이 되기 때문이다.
말이 간장공장공장장 같아서 간략한 그림으로 표현해보곘다.

이렇게 성적 A에 대해 정렬한 뒤 아래에 성적 B를 표현해보면 다음과 같다.

따라서 입력받을 때 성적 A에 대해 정렬해서 받은 뒤, 앞의 모든 값보다 작은지를 판단하면 합격할 수 있는지 확인할 수 있다.

코드:

#include <iostream>
#define MAX 100001

using namespace std;


int main()
{
	int t, n, grd1, grd2, min, count;

	cin >> t;
	for (int i = 0; i < t; i++)
	{
		int arr[MAX] = {0};
        count = 0;
		min = MAX;

		cin >> n;
		for (int j = 0; j < n; j++)
		{
			cin >> grd1 >> grd2;
			arr[grd1] = grd2;
		}
		for (int j = 1; j <= n; j++)
		{ 
			if (arr[j] < min)
			{
				++count;
				min = arr[j];
			}
		}
		cout << count << endl;
	}
}