[C++] 백준 1946번: 신입 사원 (그리디)

1946번: 신입 사원

---

문제 이해하기

 문제의 요구 사항은 다음과 같습니다.

주어진 조건에 따라 신입 사원을 선발할 때, 선발 가능한 최대 신입 사원 수를 구하여라.

 

 신입 사원 선발 조건은

서류 성적과 면적 성적 중 적어도 하나가 다른 지원자들보다 높은 지원자를 선발한다.

---

시간복잡도 어림하기

브루트 포스 알고리즘

 모든 지원자들의 성적을 담은 배열에서 현재 지원자가 다른 모든 사람들보다 적어도 하나의 성적이 높다는 것을 찾기 위해서는 전체 N명의 지원자에 대해 N - 1번 탐색을 진행해야 합니다. 따라서, 전체 탐색 횟수는 N X (N - 1)로 O(N^2)의 시간 복잡도를 가집니다.

 N의 최댓값은 100,000이고, N^2 = 10,000,000,000 이므로 제한시간 내에 문제를 해결하기 어렵습니다.

 

DP 알고리즘

  DP 배열에 i번째까지의 지원자들 중 최대로 뽑을 수 있는 신입 사원의 수를 담는다고 해봅시다. i + 1번째 인덱스를 탐색할 때, i + 1번째 지원자가 선발 가능한지를 확인하기 위해서는 처음부터 i번째 까지의 모든 지원자들과 비교해야 합니다. 이때, 탐색횟수는 등차수열의 합과 같고, 이는 O(N^2)의 시간복잡도를 가집니다. 따라서 DP 알고리즘 역시 제한 시간 내에 문제를 해결하기 어렵습니다.

 

이분 탐색 알고리즘

 한 지원자의 성적을 다른 모든 지원자와 비교해야 하므로, 탐색 범위를 반으로 줄여나가며 탐색하는 이분 탐색은 이 문제에 맞지 않는 알고리즘입니다.

 

그리디 알고리즘

 그리디 알고리즘은 정렬을 사용하는 경우가 많으므로 서류 심사를 기준으로 지원자들을 정렬한다고 합시다. 그렇다면 i번째 지원자는 i - 1번째 지원자보다 항상 서류 심사 성적이 낮습니다.(등수가 높을 수록 성적이 낮음) 따라서 면접 시험의 성적만 비교하여 현재 지원자를 선발 가능한지 판단할 수 있습니다.

 

 i번째 지원자의 선발 가능성을 판단하기 위해서는 처음부터 i - 1번째 지원자들의 면접 시험 성적과 비교해야 합니다. 이와 같은 알고리즘의 시간복잡도는 위에서 알아봤던 대로 등차수열의 합과 같으므로 O(N^2)의 시간복잡도를 가집니다.

 

 하지만 DP 알고리즘과 달리 그리디 알고리즘에서는 서류 심사를 기준으로 정렬을 했기 때문에 면접 성적만 고려해도 상관없습니다. 따라서 i번째 지원자의 선발 여부를 판단하기 위해 처음부터 i - 1번째 지원자들의 최상위 성적과 비교하여 판단할 수 있습니다. 이와 같은 알고리즘은 한 번의 비교로 선발 여부를 판단할 수 있으므로 O(N)의 시간복잡도를 가집니다.

---

알고리즘 설계하기

 이전 단계에서 설명한 내용을 요약하면 다음과 같습니다.

1. 입력을 받은 후, 서류 성적을 기준으로 오름차순 정렬한다.
2. 지원자 배열을 탐색한다.
 2.1 i번째 지원자의 면접 성적이 최상위 성적보다 낮다면 무시하고,
 2.2 그렇지 않다면 최상위 성적을 갱신한다. 

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

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

int t, n, ret, mn;
int main() {
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> t;
    int num1, num2;
    while(t--){
        cin >> n;
        vector<pair<int, int>> v;
        for(int i = 0; i < n; i++){
            cin >> num1 >> num2;
            v.push_back({num1, num2});
        }
        //서류 성적 순으로 오름차순 정렬
        sort(v.begin(), v.end());

        ret = 0, mn = 1e9; //mn은 i - 1까지의 최상위 성적
        for(int i = 0; i < n; i++){
            if(v[i].second > mn) continue; //탈락
            mn = min(mn, v[i].second);
            ret++;
        }
        cout << ret << '\n';
    }
}

 이와 같이 테스트케이스 문제들은 반드시 각 테스트케이스가 독립적으로 시행되어야 함에 주의해야합니다. 이와 같은 문제를 해결하기 위해 위 코드에서는 매 테스트케이스마다 지원자 vector를 새로 정의하여 사용했습니다.

---