백준 1946번 - 신입 사원

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

문제를 보면 서류와 면접 점수의 등수가 순서대로 주어졌다고 나와있다.

등수를 점수로 착각해서 조금 헤맸는데 항상 문제를 먼저 잘 봐야 한다고 느낀다.

그리디 문제로 이를 어떻게 해결할지 고민하다가

생각보다 간단하게 해결할 수 있었다.

동일한 등수가 없기 때문에

서류 또는 면접을 기준으로 등수대로 정렬을 하면 된다.

예를들어

문제의 보기 처럼 5명의 서류와 면접 등수를 각각 살펴보면 아래와 같다.

3 2

1 4

4 1

2 3

5 5

이를 서류 등수 순서대로 정렬 하면 아래와 같다.

1 4

2 3

3 2

4 1

5 5

여기서 중요한 점은

서류 또는 면접 등수 중에 하나라도 우위가 있으면 되기 때문에

A가 B보다 서류 등수가 낮을 때 B가 A의 면접 등수보다 높으면 된다.

즉

1 4를 먼저 포함하고

다음으로 2 3을 포함하려고 했더니

서류 등수가 낮은데 면접 등수가 더 높아서 포함 할 수 있다.

다음으로 3,2를 포함하려고 했더니

서류 등수가 낮은데 면접 등수가 더 높아서 포함 할 수 있다.

이를 반복하다가

마지막 5,5의 경우에는 서류와 면접 등수가 모두 낮기 때문에 포함시킬 수 없게 되서 4명의 신입 사원이 선발된다.

결론적으로는

서류 등수를 기준으로 정렬을 한다음에

면접 등수를 내림 차순으로 뽑을 때의 길이를 구하면 되는 문제이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    
    int T;
    cin>>T;
    
    int n;
    for(int testCase=0;testCase<T;testCase++){
        cin>>n;
        vector<vector<int>> score(n,vector<int>(2,0));
        for(int i=0;i<n;i++){
            scanf("%d %d",&score[i][0],&score[i][1]); //서류,면접 등수
        }
        
        int ans=0;
        sort(score.begin(),score.end());
        
        vector<int> select;
        select.push_back(score[0][1]);
        
        for(int i=1;i<n;i++){
            if(select[ans]>score[i][1]){
                select.push_back(score[i][1]);
                ans++;
            }
        }
        printf("%d\n",ans+1);
    }
    
    return 0;
}