[백준 1946번] 신입 사원

푼 문제

1946번: 신입 사원

문제 설명

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

풀기 전 한 생각

문제의 조건인 "다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다"라는 말을 어떻게 코드로 만들어야 할지가 잘 감이 잡히지 않았다.

어떤 A 지원자의 성적이 다른 B 지원자보다 적어도 하나는 높아야 한다. 다른 말로는 서류심사 성적과 면접시험 성적이 둘다 떨어지면 안됀다는 뜻이다.

브루트 포스 접근법

먼저 N(1 ≤ N ≤ 100,000) 명의 지원자들을 단순하게 정말 직접 비교하는 nC2의 worst 케이스를 생각해보면 가능한 경우의 수는 4,999,950,000이고, 브루트 포스로 절대 못 푼다는 것을 알 수 있다(일반적으로 최대 100만 개의 case까지가 브루트 포스로 접근하는 방식을 사용할 수 있음).

그리디 접근법

어떤 A 지원자의 성적이 다른 B 지원자보다 적어도 하나는 높아야 한다는 것을 생각해보자. 그럼 서류심사 등수가 K번째인 사람은 서류심사 등수가 1, 2, ... K-1인 사람들보다 면접 심사 성적이 가장 높아야 한다(그렇지 않으면 둘 다 떨어지는 사람이므로, 선발 불가). 가장 높아야 한다는 조건은 앞선 사람들의 면접 심사 성적 최소값보다 작아야 한다는 뜻이다. 즉, linear하게 서류심사 등수대로 지원자를 검토하면서, 면접 심사 성적 최소값을 업데이트하면 된다. 서류심사 등수가 K-1번째인 사람까지 검토했을 때의 면접 심사 성적의 최소값을 MINk-1이라고 하자. 그럼 서류심사 등수가 K번째인 사람은 MINk-1 보다 서류 심사 등수가 작아야 한다(즉, 등수가 높아야 한다). 아래 그림을 보면 이해가 쉬울 것 같다.

면접심사 등수가 높아야 하는 이유

이런 접근법이 정확히 그리디가 맞는지는 모르겠지만, 일단 간단하게 그리디라고 분류했다.

올바른 풀이 코드

버전 1

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

using namespace std;

int solution(vector<pair<int, int>> &apply) {
    // 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
    // == 서류 심사가 낮은 사람은 자신보다 서류 심사가 높은 모든 사람들 중에서 가장 면접 심사가 높아야 함
    // 면접 심사의 최소값(즉, 가장 높은 사람) 보다만 높으면 됨

    // 초기값
    int min = apply.front().second;
    int answer = 1; // 서류 1등은 반드시 선발

    for (int i = 1; i < apply.size(); i++) {
        // 최소값 업데이트가 일어나는 경우에만 선발(서류 심사가 낮은 사람이지만, 면접 심사는 높다는 뜻이므로)
        if (min > apply[i].second) {
            min = apply[i].second;
            answer++;
        }
    }

    return answer;
}

// 시간 복잡도: 입력 O(n) + sort O(nlogn) + 선발 O(n) = O(2n + nlogn) = O(nlogn)
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t) {
        int n;
        cin >> n;
        vector<pair<int, int>> apply;
        for (int i = 0; i < n; i++) {
            int test, interview;
            cin >> test >> interview;
            apply.push_back(make_pair(test, interview));
        }

        sort(apply.begin(), apply.end(), less<>()); // 서류, 순위로 오름차순 정렬(순위가 낮을 수록 잘 본 것)

        cout << solution(apply) << "\n";
        t--;
    }
}

해당 로직을 사용하니 메모리는 4192 KB, 시간은 512 ms가 소요되었다. 다른 정답자들을 보면 두 자리대의 시간 복잡도를 기록한 사람들도 많은 것으로 보아 훨씬 더 줄일 수 있을 것 같은데, 이 부분은 조금 더 고민을 해봐야겠다.

버전 2

이 글을 쓰면서 방금 깨달았는데, 백트래킹을 추가하면 시간을 조금 더 줄일 수 있다. 면접심사 성적 1등이 나오면 그 아래부터는 면접심사 성적이 더 높은 것이 불가능하므로 여기서 for문을 break하면 된다.

백트래킹이 이루어지는 시점

수정된 코드는 다음과 같다.

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

using namespace std;

int solution(vector<pair<int, int>> &apply) {
    // 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
    // == 서류 심사가 낮은 사람은 자신보다 서류 심사가 높은 모든 사람들 중에서 가장 면접 심사가 높아야 함
    // 면접 심사의 최소값(즉, 가장 높은 사람) 보다만 높으면 됨

    // 초기값
    int min = apply.front().second;
    int answer = 1; // 서류 1등은 반드시 선발

    for (int i = 1; i < apply.size(); i++) {
        if (min == 1) {
            break;
        }
        // 최소값 업데이트가 일어나는 경우에만 선발(서류 심사가 낮은 사람이지만, 면접 심사는 높다는 뜻이므로)
        if (min > apply[i].second) {
            min = apply[i].second;
            answer++;
        }
    }

    return answer;
}

// 시간 복잡도: 입력 O(n) + sort O(nlogn) + 선발 O(n) = O(2n + nlogn) = O(nlogn)
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t) {
        int n;
        cin >> n;
        vector<pair<int, int>> apply;
        for (int i = 0; i < n; i++) {
            int test, interview;
            cin >> test >> interview;
            apply.push_back(make_pair(test, interview));
        }

        sort(apply.begin(), apply.end(), less<>()); // 서류, 순위로 오름차순 정렬(순위가 낮을 수록 잘 본 것)

        cout << solution(apply) << "\n";
        t--;
    }
}

이제 시간이 504 ms로 조금 줄었다. 사실 이 방식은 데이터의 특성에 따라서 효과가 크게 달라질 수 있기 때문에, 시간을 좀 더 줄이고 싶으면 알고리즘 측면에서의 개선이 필요해 보인다. 이 점은 더 고민해봐야 할 것 같다.

배운 점

"적어도 하나가 다른 지원자보다 떨어지지 않는 지원자만 선발"라는 조건을 "둘 다 떨어지는 지원자는 선발하지 않음"으로 해석하는 방법을 배웠다. (사실 확률과통계를 공부할 때 많이 써먹었던 방식인데 그 동안 수학공부를 안 하고 살았더니 바로 까먹은 듯)