메모리
시간
1776 KB
704 ms
문제 풀이
이 문제는 신입사원을 뽑을때 한 사람 당 두가지 성적을 두고
다른 모든 지원자와 비교해 적어도 하나의 성적이 다른 지원자보다 떨어지지 않는 사람만 선발하여
최대 합격가능한 인원수를 구하는 문제이다.
다시 말하자면 두개 성적을 1번성적, 2번 성적이라 부를때
a사원 보다 1번 성적이 높은 사람 중에는 a의 2번 성적이 가장 높아야 a사원을 선발할 수 있다는 뜻이다.
1번과 2번 성적 둘다 a 사원 보다 높은 지원자가 있다면 a 지원자는 합격할 수 없다
이 문제를 해결하기 위해 우선 1번 성적 기준으로 정렬을 해준 뒤
가장 순위가 높은(가장 성적이 높은) 2번 성적을 comp에 담아주고
z 번째 지원자의 2번째 성적과 comp(z 번째 지원자 이전에 나온 지원자들의 2번 성적 등수 중 가장 높은 등수)를 비교해가며 comp보다 순위가 더 높다면 채용이 가능한 기준 충족으로 count를 올려준다.
첫번째 인덱스는 1번 성적이 1등으로 무조건 채용 가능해 count 는 1부터 시작한다.
Code
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int t;
pair<int, int> emp[100000];
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
int n;
scanf("%d", &n);
for (int j = 0; j < n; j++)
{
scanf("%d%d", &emp[j].first, &emp[j].second);
}
sort(emp, emp + n);
int comp = emp[0].second;
int count = 1;
for (int z = 1; z < n; z++)
{
if (emp[z].second < comp)
{
count++;
comp = emp[z].second;
}
}
printf("%d\n" ,count);
}
return 0;
}
C++
복사
