[백준 1946] 신입 사원 cpp

문제
신입사원을 채용하려고 할 때 서류심사 성적과 면접시험 성적을 고려한다. 이때 둘 중의 한 점수라도 다른 지원자보다 높다면 채용을 하게 된다. 즉 어떤 지원자가 자기보다 서류와 면접 성적이 높다면 그 지원자는 절대 채용될 수 없다. 이 회사가 채용할 수 있는 최대 사원의 수를 구하라.

입력
첫째 줄에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에 지원자의 숫 N
N은 1이상 100,000이하이다.
이후 N개의 서류심사 성적과 면접 성적 순위가 입력된다.
동석차는 없다.

출력
각 테스트 케이스마다 최대 인원 수를 출력

---

먼저 이런 수와 관련된 것들이 나열되어있으면 정렬을 한 다음에 풀면 어떨까? 라는 생각이 들었다.

그래서 서류심사 석차를 기준으로 오름차순 정렬을 했다.

그렇게 되면 첫 번째 지원자는 무조건 합격이다. 왜냐하면 면접 등수를 보지 않아도 무조건 면접등수는 제일 높기 때문이다. 따라서 첫 번째 지원자의 면접 등수보다 높은 사람만 채용이 될 수 있다.

 

서류는 이미 오름차순으로 정렬되어 있기 때문에 면접 등수로 채용을 결정할 수 있다.

결론적으로 풀이는 다음과 같다.

1. 첫 번째 지원자의 면접 등수를 cut_line에 기록한다.

2. cut_line보다 숫자가 낮은 사람이 있으면 최종해를 증가시키고 

3. cut_line을 그 지원자로 갱신한다.

4. 위의 과정을 반복하면 채용되는 사원 수가 나온다.

 

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;


int main()
{
	int test_case;
	cin >> test_case;

	while (test_case--) {
		int N;
		int answer = 1;
		cin >> N;
		vector<pair<int, int>> v;
		for (int i = 0; i < N; i++) {
			int a, b;
			cin >> a >> b;
			v.push_back({ a,b });
		}

		sort(v.begin(), v.end());

		int cut_line = v[0].second;
		for (int i = 1; i < N; i++) {
			if (cut_line > v[i].second) {
				cut_line = v[i].second;
				answer += 1;
			}
		}

		cout << answer << endl;
	}
	
	
	
	return 0;
}