1946

백준 1946번

Link: 1946번: 신입 사원

---

문제 설명

오늘도 Greedy문제.

문제 이해하는데 시간이 좀 오래걸렸다.

이해하고 나서 풀어보려는데 처음에는 두 등수의 평균을 구한 다음 평균이 높은 절반끼리 비교하는 방식으로 구현했는데, 일단 시간초과가 났다.

방문 여부를 표시하고 조건에 안맞으면 반복문 중간에서 나가는 방식으로 보완했는데, 이렇게 푸니까 이젠 답이 틀리더라.

그 다음엔 각각의 등수가 1인 경우들은 반드시 포함시키고, 이 둘에 대해 비교하며 카운트를 늘려가는 방식으로 풀어봤는데, 역시 틀렸다.

한참 고민하며 반례 찾으러 질문게시판에 들어가봤는데, 반례 찾다가 다른사람의 아이디어를 보고 힌트를 얻어 풀 수 있었다.

핵심은 한가지 등수로 오름차순 정렬을 하는 것.

이렇게 하면 두가지 등수 중 한가지 등수만 비교하면 풀린다.

나머지 한 등수에 대해 정답에 포함시킨 바로 앞 등수보다 크면 포함시키지 않고, 반대의 경우 작은 등수로 바꿔주고 카운트를 하나 늘린 후 이를 반복하는 방식으로 풀 수 있었다.

아이디어를 짜내보려고 노력한 것까지는 좋았던 것 같으나 핵심을 찾는데에는 도달하지 못했다.

심지어 한가지 등수로 오름차순 정렬하는것까지는 했는데 그 다음을 생각해내지 못했다는 점이 아쉬웠다.

---

정답 코드

//
// Created by Keith_Lee on 19/02/2019.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct candidates{
    int doc, interview;
};

bool compare(candidates &a, candidates &b){
    if(a.doc > b.doc){
        return false;
    }
    return true;
}

int main(){
    int T;

    cin >> T;

    for(int test=0; test<T; test++){
        int N;

        cin >> N;

        vector<candidates> applicants;

        for(int i=0; i<N; i++){
            int doc, interview;

            cin >> doc >> interview;

            applicants.push_back({doc, interview});
        }

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

        int count = 1;

        int standard = applicants[0].interview;

        for(int i=1; i<applicants.size(); i++){
            if(standard > applicants[i].interview){
                standard = applicants[i].interview;
                count++;
            }
        }

        cout << count << '\n';
    }

    return 0;
}

---