[백준/c++] BOJ 1946 - 신입사원

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

1946번: 신입 사원

 

문제 설명

주식회사의 지원자는 서류 심사와 면접 시험을 본다. 서류 심사의 순위와 면접 시험의 순위가 주어질 때, 어떤 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 즉, 두 심사의 순위가 지원자보다 더 높은 사람이 있을 경우, 해당 지원자는 탈락한다. 각 테스트 케이스에 대해서 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

 

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 20)가 주어지며, 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 <= N <= 100,000)이 주어진다. 성적의 순위는 1위부터 N위까지 동석차 없이 결정된다.

 

해결

두 성적은 pair로 vector에 받아 주었다. vector의 원소로 pair가 있을 경우, sort하게 되면 pair의 첫번째 원소를 기준으로 정렬된다. 즉, 정렬 후 벡터의 idx = 0 원소는 서류 심사의 1등이 된다.

 

서류 심사의 1등은 다른 누구랑 비교해도 서류 심사의 성적에서 이기므로, 떨어질 수 없는 사람이다.

또한, 그 뒤의 사람들은 서류 심사 1등과 비교했을 때 면접 시험의 순위도 낮다면, 선발에 떨어질 수 있다.

 

따라서 서류 심사의 2등부터 N등까지 기준 사람(처음엔 서류 심사의 1등)과 순서대로 비교하면서 면접 성적이 더 안 좋은 사람은 탈락하고, 더 좋은 사람은 합격시키며 기준 사람을 갱신해 주었다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m;
		vector<pair<int, int>> v;
		int a, b, ans = 1;
		for (int j = 0; j < m; j++) {
			cin >> a >> b;
			v.push_back(make_pair(a, b));
		}
		sort(v.begin(), v.end());
		
		int idx = 0;

		for (int j = 1; j < m; j++) {
			if (v[idx].y > v[j].y) {
				ans++;
				idx = j;
			}
		}

		cout << ans << "\n";
	}
}