백준 1946번 신입사원

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

 

문제 분류 - 그리디 알고리즘

 

풀이

우선 문제를 읽고, 지원자의 숫자 N의 제한이 10만이라는 점을 보고 빠르게 O(n^2)로 모든 지원자들을 계속해서 비교해나가는 풀이는 포기했다.

그렇다고 O(nlgn)의 방법으로 이분탐색을 하자니.. 딱히 절반 절반 줄여나갈 포인트가 생각이 안 났고

그다음 생각난 것이 아래와 같은 풀이이다.

 

먼저, 입력에서 각 지원자들의 성적 순위가 주어졌기 때문에 본능적으로 무언가 정렬을 해야 할 듯하다.

따라서 정렬을 하고 보니 두 성적 중 아무 성적이나 1위를 하고 있는 신입 사원은 어떻게 뽑든 반드시 선발되기 마련이다. 만약 성적이 (1, x)인 신입 사원이 선발이 되지 않았다면, 선발될 수 있는 신입은 (z, k) (단, k < x)인 모든 인원이 되는데, 이들은 (1, x)가 선발되어도 동일한 숫자를 유지한다. 따라서 무조건 뽑는 게 이득이다.

 

이렇게 1위인 신입을 뽑고 나면 이제 맨 앞에 있는 2위는 x보다 작기만 하면 무조건 선발되기 마련이다. 이 사원의 성적을 (2, y)라 하면 그다음은 y보다 작은 수를 뽑아야 하고.. 반복이다.

 

정리하자면

• 한 시험 성적을 기준으로 정렬 -> O(nlgn)
• 맨 앞 사원 (1, x)를 선택한다. 이때 최소 성적을 x로 초기화
• 이후 (2, y) (y < x)를 선택 후 y를 최소 성적으로 초기화
• 3번째 과정을 반복 

이렇게 진행해서 선택된 인원을 답으로 출력한다.

 

소스 코드

 

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<pair<int, int> >v;
        for (int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            v.push_back(make_pair(y, x));
        }
        sort(v.begin(), v.end());
 
        int ans = 1;
        int temp = v[0].second;
        for (int i = 1; i < n; i++)
        {
            if (v[i].second < temp)
            {
                ans++;
                temp = v[i].second;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}