백준(BOJ) 1946번: 신입 사원
문제링크: https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
www.acmicpc.net
나의 풀이:
서류 성적순으로 정렬한다.
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;
}
