백준(BOJ) 1946번: 신입 사원

문제링크:   https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

나의 풀이:

서류 성적순으로 정렬한다. 

1등을 뽑은 후(cnt++) 1등의 면접 성적보다 높은 순위의 지원자를 고른다.

(반복) 그 지원자를 뽑은후(cnt++)  N까지 그 지원자의 면접성적보다 높은 순위의 지원자를 고른다.

 

주의할점:

서류순으로 먼저 정렬하니 문제 풀기 편했다.

 

코드

 

#include  <iostream>
#include  <algorithm>
using namespace std;

const int MAX = 100000;
int N;
pair<int,int> applicant[MAX];
int main()
{
int T;
cin >> T;
while (T--)
{
int cnt = 0;
cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> applicant[i].first >> applicant[i].second;
}
sort(applicant, applicant + N);
cnt++; // 1등을 뽑는다.
int bestscore = applicant[0].second;
for (int i = 1; i < N; ++i) // 현재 뽑힌사람보다 서류순위는 낮지만(정렬됨) 면접순위가 높은 사람을 찾는다.
{
if (applicant[i].second < bestscore)
{
cnt++;
bestscore = applicant[i].second; // 뽑힌사람의 면접순위로 갱신한다.
}
}
cout << cnt << endl;
}
return 0;
}