[C++] 백준 온라인 저지 1946번 신입 사원 풀이

진영 주식회사의 신입 사원 선발을 도와주는 문제

 

---

문제의 조건

 

1. 진영 주식회사는 신입 사원 지원자들의 서류 점수와 면접 점수를 매겼다. 

 

2. 진영 주식회사에서 신입 사원을 선발하는 기준은

어떤 지원자가 다른 지원자보다 적어도 한 가지는 더 높은 순위를 받아야 한다는 것이다. 

서류 점수라도 더 높던가 면접 점수라도 더 높던가

그렇지 않고 둘 다 다른 지원자보다 낮으면 탈락

 

3. 테스트 케이스가 여러 개 주어질 때 각 케이스별로 최대한 많이 선발할 수 있는 신입 사원의 수를 구해서 출력하기

 

---

풀이 과정

 

처음엔 서류 점수를 기준으로 오름차순 정렬을 하면 되겠다 까지는 생각을 했는데

그 뒤로 비교 조건을 어떻게 해야할 지 감이 잘 안 와서 힌트를 봤습니다. 

 

과정

1. 지원자들의 점수를 pair<서류 점수, 면접 점수> 구조체를 이용해서 저장한다. 

 

2. 서류 점수를 기준으로 오름차순 정렬을 한다.

(sort 함수 쓰면 key값 기준 오름차순 정렬이라 따로 비교 함수는 작성하지 않아도 됨)

 

3. 서류 1등인 지원자는 다른 지원자들보다 항상 서류 점수가 높다. 

그렇기 때문에 항상 채용 조건에 부합한다.

서류 1등은 무조건 채용함

 

4. 서류 1등을 채용하고 나면 다음 순위 지원자들을 비교해야 하는데 

서류 2등이 채용되려면 서류 1등보다 면접 점수가 높아야 한다. 

그렇기 때문에 서류 1등의 면접 점수를 저장해 놓고 서류 2등과 비교한다. 

 

5. 서류 2등이 1등보다 면접 점수가 높으면 채용할 수 있지만 낮으면 채용하지 않는다. 

서류 2등이 채용되면 서류 3등과 비교해야 하니까 서류 2등의 면접 점수를 저장해 놓고 서류 3등과 비교한다. 

서류 2등이 채용되지 않으면 서류 1등의 면접 점수와 서류 3등의 면접점수를 비교해서 4, 5번 과정을 반복한다. 

 

6. 이렇게 해서 최종적으로 나온 결과를 출력

 

---

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int T;
    cin >> T;
    
    for (int i = 0; T > i; i++)
    {
        int N;
        cin >> N;
        vector<pair<int, int>> testCases;
        for (int j = 0; N > j; j++)
        {
            int letter, interview;
            cin >> letter >> interview;
            testCases.emplace_back(make_pair(letter, interview));
        }
        
        sort(testCases.begin(), testCases.end());
        
        int answer = 1;
        int score = testCases[0].second; //서류 1등의 면접순위부터 시작 
        for (int j = 1; testCases.size() > j; j++)
        {
            if (score > testCases[j].second)
            {
                //다음 등수의 면접 순위가 더 높다면 정답 증가시키고 비교 대상 면접 순위를 갱신한다.
                answer++;
                score = testCases[j].second;
            }
        }
        
        cout << answer << endl;
    }
    
    return 0;
}