백준 1946번 신입 사원

문제 링크입니다: https://www.acmicpc.net/problem/1946

그리디(greedy) 알고리즘 문제였습니다.

A라는 사람의 서류심사 성적과 면접시험 성적이 B란 사람보다 둘 다 열세라면 채용을 하지 않는다는 것이 문제의 조건이였습니다.

따라서, 알고리즘은 아래와 같습니다.

1. 신입사원들의 서류심사 성적을 기준으로 오름차순 정렬을 합니다.

2. 정렬한 뒤 첫 번째 사원은 서류심사 성적이 일등이므로 무조건 채용을 합니다.

3. 첫 번째 사원의 면접시험 성적을 기록하고 두 번째 사원부터 N 번째 사원까지 반복문을 돌리면서 기록한 면접시험 성적보다 우세한 사람을 찾아 채용합니다.

4. 3번에서 채용한 사람의 면접시험 성적을 기록하고 3번을 반복합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100000;

 

int N;

pair<int, int> employee[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 cin >> N;

 

                 for (int i = 0; i < N; i++)

                         cin >> employee[i].first >> employee[i].second;

 

                 sort(employee, employee + N);

 

                 int result = 1; //첫 번째 사원은 무조건 선발(서류심사 성적 1등)

                 int interviewRank = employee[0].second; //첫 번째 사원의 인터뷰 심사 성적

 

                 for (int i = 1; i < N; i++)

                 {

                         //기존의 인터뷰 심사 성적보다 높은 성적인 사람 채용

                         if (employee[i].second < interviewRank)

                         {

                                 result++;

                                 //인터뷰 심사 성적 업데이트

                                 interviewRank = employee[i].second;

                         }

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~