[백준] #1946 신입사원

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

간단한 그리디 알고리즘 문제로, 조금만 다르게 생각해본다면 쉽게 풀 수 있는 문제다.

---

• 풀이

가장 단순하게 브루트포스를 이용하여 모든 인덱스를 전수조사하는 방법도 있겠지만, 그렇게 될 경우 반복문 2개를 사용하게 되어 연산 횟수가 10B 가 된다. 따라서, 반복문 하나만으로 해결해야 하는 문제이다.

 

다음 특성만 생각하면 무척 쉬운 문제이다.

1. 지원자 중, 두 심사의 등수 모두 본인보다 높은 사람이 한명이라도 있다면, 탈락한다.
2. 두 심사중 하나만이라도 다른사람보다 등수가 높다면, 합격한다.
=> 어느 하나의 심사를 기준으로 정렬된 벡터에서 다른 한 심사의 최솟값을 갱신시키는 인덱스는 합격한다.

---

• 구현

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

using namespace std;

int main(void) {
    int T;
    cin >> T;

    while (T-->0) {
        int N, cnt = 1;
        cin >> N;

        vector<pair<int, int>> v;
        for (int i = 0; i < N; i++) {
            int a, b;
            cin >> a >> b;
            v.push_back(make_pair(a,b));
        }   //벡터 구성

        //브루트포스 방식으로 각 인덱스 전수조사 -> 시간 초과 발생. 연산 횟수 최대 10B
        /*for (int i = 0; i < v.size(); i++) {
            pair<int,int> target = v[i];

            for (int j = 0; j < v.size(); j++) {
                if (target.first > v[j].first && target.second > v[j].second) {
                    cnt++;
                    v.erase(v.begin() + i);
                    i--;
                    break;
                }
            }

        }
        cout << N-cnt << '\n';*/

        sort(v.begin(), v.end());

        int target = v[0].second;
        for (int i = 1; i < v.size(); i++) {
            if (target > v[i].second) {
                cnt++;
                target = v[i].second;
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}

---

처음 시도에서 브루트포트 방식으로 풀다 시간초과, 두번째 시도에선 최솟값을 갱신시키지 않아서 틀렸다.