[C++][백준 BOJ]1946_신입 사원.

문제 번호

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

1946번: 신입 사원

 

 

알고리즘 분류

 그리디 (greedy).

 

문제 풀이

 그리디 알고리즘을 사용하여 문제를 해결 할 수 있다.

 처음에는 문제의 내용을 잘못이해 하여서 가장 우수한 사람을 채용하지 않더라도 가장 많은 수의 사람을 채용해야 하는 줄 알았다. 그래서 모든 지원자를 탐색하면서 각 지원자들이 몇명보다 우위에 있는지를 검사하고, 그중에서 가장 많이 나온 숫자의 개수가 정답인줄 알았다. 

 

1. 지원자들을 서류성적을 기준으로 오름차순으로 정렬한다. 

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.first < b.first;
}

sort(employee.begin(), employee.end(), compare);

 

2. 서류성적 1등은 무조건 채용이다. 그 후 1등의 면접점수를 cutline으로 설정한다. 

    int answer=1;
    int cutline = employee[0].second;

3. 서류성적 1등을 제외한 모든 지원자를 검사하면서 서류성적 1등의 면접점수등수 보다 더 높은 등수를 갖은 사람이 나오면 cutline을 그 사람의 등수로 바꿔준다.

for(int i=1; i<employee.size(); i++)
    {
        if(employee[i].second < cutline)
        {
            cutline = employee[i].second;
            answer++;
        }
    }

 

4. 이 과정을 반복하여 총 인원 수 를 구한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.first < b.first;
}

int Solution(vector<pair<int,int>> employee)
{
    sort(employee.begin(), employee.end(), compare);
    
    int answer=1;
    int cutline = employee[0].second;
    for(int i=1; i<employee.size(); i++)
    {
        if(employee[i].second < cutline)
        {
            cutline = employee[i].second;
            answer++;
        }
    }

    return answer;    
}

int main()
{
    int TC; cin >> TC;
    while(TC--)
    {
        int num; cin >> num;
        vector<pair<int,int>> employee;
        for(int i=0; i<num; i++)
        {
            int a, b; cin >> a >> b;
            employee.push_back( {a,b} );
        }
        cout << Solution(employee) << '\n';
    }
    return 0;
}

 

특이사항

 문제에서 주어진 조건들을 제대로 파악하는것이 중요하다. 문제 자체는 어렵지 않았으나 문제에서 말하고자하는 바를 잘못 이해하여 혼자서 어렵게 만들었다.