[C/C++] 백준 #1946 신입 사원(탐욕 기법)

신입사원의 채용 기준은 다른 모든 면접자들의 성적과 비교해서 하나라도 우수한 직원을 뽑는 것입니다.

 

interview

 

문제의 뜻을 잘 이해하지 않으면 풀기 어려운 문제입니다.

성적은 두가지가 있는데, 이 두가지의 성적은 모두 동차 없이 순위가 정해집니다.  N명의 면접자가 있다면, 1위부터  N위까지말이죠.

예를 들어서 3명의 면접자가 있고, 순위가 (1, 3) (2, 2) (3, 1) 이었다면, (1, 3)위 한 사람은 다른 두 직원에 비해서 첫번째 성적이 좋으므로 채용됩니다.  (2, 2)한 면접자는 (1, 3) 면접자에 비해서는 두번째 시험성적이, (3, 1) 면접자에 비해서는 첫번째 시험성적이 좋아서 채용되죠.  (3, 1) 면접자는 다른 두 면접자에 비해서 두번째 성적이 좋아서 채용됩니다.

 

이것을 저는 탐욕적 기법을 통해서 풀었습니다.

1) 첫번째 성적으로 정렬합니다.

2) 두번째 성적의 최소값을 N+1로 설정합니다.

3) 정렬된 모든 원소에 대해서,

    3-1) 두번째 성적이 최소값보다 작으면, 채용합니다.  그리고 최소값을 지금값으로 변경합니다.

이렇게 채용될 사람들을 모두 가릴 수 있습니다.

 

정렬을 했기 때문에 앞의 면접자들은 뒤의 면접자들에 비해서 첫번째 성적이 우수합니다.  즉, 뒤의 면접자가 채용되기 위해서는 앞의 면접자중 두번째 성적이 가장 좋은 사람보다 더 좋은 성적을 가져야 하죠.  뒤의 면접자는 신경쓰지 않아도 되는 것이 뒤의 면접자보다 첫번째 성적이 더 우수하기 때문이죠.  이렇게 함으로써 모든 면접자들과 비교했을 때, 적어도 한개의 성적은 우수하죠.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1946
//        - by Aubrey Choi
//        - created at 2019-11-18
//------------------------------------------------
#include <stdio.h>
#include <algorithm>
struct Order { int a, b; };
bool cmp(Order &a, Order &b) { return a.a<b.a; }
int main()
{
    Order v[100000]; int t, n, i, min, ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++) scanf("%d%d",&v[i].a,&v[i].b);
        std::sort(v,v+n,cmp);
        for(i=0,min=100001,ans=0;i<n;i++) if(v[i].b<min) min=v[i].b,ans++;
        printf("%d\n",ans);
    }
}