문제접근🤔

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙
서류심사 성적이든 면접심사 성적이든 둘 중 1등인 사람은 무조건 다른 지원자보다 우수한 성적이기 때문에 선발이 보장
서류심사 성적을 기준으로 정렬을 해주게 되면 서류심사의 1등을 찾을 수 있게 되고 그 다음 선발의 기준은 서류심사 1등 선발자의 면접시험 등수보다 더 나은 사람이면 된다.
여기서 주의할점은 서류심사 1등의 면접심사 등수가 계속 다음 선발의 기준이 되는 것이 아니라는 점이다.

서류심사 1등의 서류등수로 다음 선발자를 찾게 되면 그 다음 선발의 기준은 이전 선발자의 면접심사 등수보다 더 나아야 한다.

그렇지 않으면 기존 원칙에 위반이 되는 상황이 벌어짐(아래 예시 참고)
예시로 확인을 해보자
```
1번 지원자 : 3 6 
2번 지원자 : 7 3
3번 지원자 : 4 2
4번 지원자 : 1 4
5번 지원자 : 5 7
6번 지원자 : 2 5
7번 지원자 : 6 1

-> 정렬 후
4번 지원자 : 1 4 //선발. 다음 선발의 기준은 면접 등수가 4등 보다 우수
6번 지원자 : 2 5 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
1번 지원자 : 3 6 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
3번 지원자 : 4 2 //선발. 선발기준인 면접 등수가 4등 보다 우수. 다음 선발의 기준은 면접 등수가 2등 보다 우수
5번 지원자 : 5 7 //미선발. 선발기준인 면접 등수가 2등 보다 떨어짐
7번 지원자 : 6 1 //선발. 선발기준인 면접 등수가 2등 보다 우수. 다음 선발의 기준은 면접 등수가 1등 보다 우수(없음)
2번 지원자 : 7 3 //미선발. 선발기준인 면접 등수가 1등 보다 떨어짐
```
<aside> 💡 선발 기준이 계속 업데이트 되어야 하는 이유(업데이트 하지 않으면 ???)

4번 지원자 : 1 4 //선발. 다음 선발의 기준은 면접 등수가 4등 보다 우수 6번 지원자 : 2 5 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐 1번 지원자 : 3 6 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐 3번 지원자 : 4 2 //선발. 선발기준인 면접 등수가 4등 보다 우수. 선발 기준은 여전히 4등 5번 지원자 : 5 7 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐 7번 지원자 : 6 1 //선발. 선발기준인 면접 등수가 4등 보다 우수. 선발 기준은 여전히 4등 2번 지원자 : 7 3 //선발. 여기서 문제가 발생

이런식으로 업데이트를 하지 않으면 맨 마지막의 2번 지원자도 선발을 하게 된다. 그렇게 되면 2번 지원자의 경우 기존에 뽑힌 4번 지원자와 비교했을때는 면접심사 등수가 우수하여 원칙을 위배하지 않게 되지만, 기존에 뽑힌 나머지 두 지원자(3번, 7번)와 비교했을때는 원칙을 위배하게 된다.

</aside>

놓쳤던 부분😅

합격할 수 있는 모든 신입사원들은 서로에 대해서 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 을 성립해야함.
```
1번 지원자 : 3 6
2번 지원자 : 7 3
3번 지원자 : 4 2
4번 지원자 : 1 4
5번 지원자 : 5 7
6번 지원자 : 2 5
7번 지원자 : 6 1
```
- 위와 같은 입력이 들어왔을때, 2번 지원자의 서류등수가 7등이기 때문에 7번 지원자를 제외한 모든 지원자가 선발될 수 있는 것이 아니다.
- 예를 들어, 1번 지원자가 뽑히게 된다면 그 이후 뽑히는 지원자들의 점수는 서류등수가 3등 보다 우수하거나 면접등수가 6등 보다 우수해야한다.

코드😁

2800 KB

504 ms

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

int t;
int n;
std::vector<std::pair<int, int> > score;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	std::cin >> n;
	score.resize(n);
	for (int i = 0; i < n; i++)
		std::cin >> score[i].first >> score[i].second;
}

void solution()
{
	int limit;
	int count = 1;

	sort(score.begin(),score.end());
	limit = score[0].second;
	for (int i = 1; i < n; i++)
	{
		if (limit > score[i].second)
		{
			++count;
			limit = score[i].second;
		}
	}
	std::cout << count << "\\n";
}

int main(void)
{
	input_setting();
	std::cin >> t;
	for (int i = 0; i < t; i++)
	{
		input();
		solution();
	}
	return (0);
}