백준 1946 신입 사원 C++ 문제 풀이
풀이
접근
두 가지의 성적을 비교하여 신입 사원 간 우위를 확인하기 위해서는
서류 성적을 먼저 정렬할 필요가 있어 보입니다.
그 후 면접 성적을 비교하여 가장 많은 신입 사원의 수를 계산해야 합니다.
정렬 후 첫 번째 신입사원은 다른 신입사원보다 반드시 서류 성적이 뛰어날 것이므로
면접 성적이 어떻게 되었든 반드시 합격하는 신입사원입니다. (정렬 후 그리디한 접근이 이 문제에서 반드시 최대의 경우의 수를 도출하는 이유입니다.)
첫 번째 신입 사원과 두 번째 신입사원의 면접 성적과 비교하였을 때,
만약 첫 번째 신입사원보다 면접 성적이 좋은 경우 두 번째 신입사원을 비교 기준으로 변경합니다.
달리 얘기해서, 이미 서류 성적이 낮은 세 번째 네 번째 ... 신입 사원들은 두 번째 신입사원보다 면접 성적이 높기만 하면 합격입니다.
만약 첫 번째 신입사원보다 면접 성적이 낮을 경우 첫 번쨰 신입사원을 비교 기준으로 유지합니다.
즉, 첫 번째 신입사원의 면접 성적과 세 번째 신입사원의 면접 성적과 비교합니다.
위 (그리디한) 탐색을 반복하여 합격 가능한 신입 사원 최대의 수를 도출할 수 있습니다.
솔루션
아래 솔루션보다 더 깔끔하게 짤 수 있지 않을까.. 생각이 듭니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int T, N;
int main () {
cin >> T;
for(int t=0; t<T; t++){
cin >> N;
vector < pair<int, int> > V;
// 입력
for(int n=0; n<N; n++){
int a, b;
cin >> a >> b;
V.push_back(make_pair(a, b));
}
// 계산 및 출력
sort(V.begin(), V.end());
int answer = 1;
int cur = V[0].second;
for(pair<int, int> P : V){
if(cur == P.second){
continue;
}
if(cur > P.second){
cur = P.second;
answer += 1;
}
}
cout << answer << '\n';
}
return 0;
}