백준 1946 - 신입사원 - 그리디알고리즘

문제

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

풀이전략

1. 다른 모든 지원자와 비교하였을 때 성적 & 면접이 다 높아야 한다.
2. 1 <= N <= 100000이므로 N^2은 불가하다.
3. 처음엔 1등이 가지고 있는 두 값을 찾고 그 값들보다 작은 값들을 없애려고 했지만 이는 틀린 답이다. 따라서 먼저 성적을 정렬을 하고, 이후 면접에서 bound를 설정하여 풀어야한다.

코드

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

int T, N;

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

int main(){

    // freopen("../input.txt","rt",stdin);
    scanf("%d",&T);
    vector<pair<int, int> > people;
    for(int t=0; t<T; t++){
        scanf("%d",&N);
        people.clear();
        int ta, tb;
        
        for(int i=0; i<N; i++){
            scanf("%d %d",&ta, &tb);
            people.push_back(make_pair(ta,tb));
        }
        /// sort 함수 사용할때 반드시 함수포인터 넣어주고, algorithm헤더 써야함을 잊지말기.
        sort(people.begin(), people.end(), ccomp);

        int bound = people[0].second;
        int cnt = 0;
        for(int i=1; i<N; i++){
            if(people[i].second > bound){
                cnt++;
            }
            else bound = people[i].second;
        }
        printf("%d\n",N-cnt);
        // 이렇게 짠 코드의 반례
        // 만약 1 4, 4 1, 2 2, 3 3 이 있을경우 3, 3 은 탈락이다 왜냐하면 2, 2 가 있기 때문이다. 
        // 집중해서 반례찾는것에 더 연습해야겠다. 
        // int aTopB = 0, bTopA = 0;
        // for(int i=0; i<N; i++){
        //     scanf("%d %d",&ta, &tb);
        //     if(ta == 1) aTopB = tb;
        //     if(tb == 1) bTopA = ta;
        //     people.push_back(make_pair(ta, tb));
        // }
        // int cnt = 0;
        // for(int i=0; i<N; i++){
        //     if(people[i].first > bTopA || people[i].second > aTopB) cnt++;
        // }
        // printf("%d\n",N-cnt);
    }
    return 0;
}

소감

문제풀때 반례를 생각하지 못하였다..... 너무 당연한건데 생각 못했다. 앞으로는 더 잘 할수있도록 이번 문제를 계속 곱씹어야겠다!.