[C++]Baekjoon 1946번: 신입 사원

1. 문제

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

1946번: 신입 사원

 

각 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다.

 

서류심사 성적, 면접 성적 둘 모두가 다른 지원자보다 낮은 지원자가 있다면,

 

그 지원자는 선발 될 수 없다.

 

이 조건을 만족시키면서 선발할 수 있는 최대 인원수를 출력하는 문제이다.

 

2. 풀이

STEP1. 각 지원자의 서류심사 성적, 면접 성적의 순위를 벡터에 받아 저장한다.

 

그리고 sort()를 활용하여 정렬을 한다.

 

sort()의 결과로 서류성적이 좋은 지원자 순으로 정렬이 될 것이다.

 

STEP2. 이 문제 해결의 핵심이 되는 부분이다.

 

서류성적이 1등인 지원자는 누구와 견주어도 뒤지지 않으므로 무조건 합격시키고(cnt = 1로 시작)

 

서류성적이 2순위인 지원자부터 상위 순위자와 면접 성적을 비교해주면 되는데,

 

서류성적 상위 순위자보다 면접 성적이 좋다면 이 지원자는 합격할 수 있다!

 

(서류는 뒤지지만 면접은 앞서기 때문)

 

서류성적 마지막 순위자까지 비교를 한 후에는 cnt를 출력해주고,

 

STEP3. 다시 cnt를 1로 초기화 한 후, 다음 테스트 케이스를 수행한다.

 

3. 코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int test_case; // 테스트 케이스의 횟수

    int rep; // 지원자의 숫자

    int n, m; // 지원자의 서류심사 성적, 면접 성적

    int cnt = 1; // 합격할 수 있는 인원 수(최소 1명(서류 1등)은 합격하니까 1로 초기화)

    vector<pair<int, int>> v; // 성적을 담아놓을 벡터

    cin >> test_case;

    for (int i = 0; i < test_case; i++) { // 성적 입력받아서 벡터에 저장

        cin >> rep;

        for (int j = 0; j < rep; j++) {

            cin >> n >> m;

            v.push_back(make_pair(n, m));

        }

        sort(v.begin(), v.end()); // 벡터를 정렬하면 서류심사 성적이 좋은 순으로 정렬됨

        int temp = v[0].second; // 임시로 면접 성적을 저장 할 변수

        for (int k = 1; k < rep; k++) { // 서류 2등부터 꼴등까지 반복문을 통해 비교

            if (v[k].second < temp) { // 만약 서류 k등인 사람이 상위 등수 사람보다 면접을 잘 봤다면

                cnt++; // 그 사람을 선발한다

                temp = v[k].second; // 선발 기준이 되는 면접 접수 갱신(하위 등수 후보자는 상위등수 보다 면접을 더 잘봐야 함으로 커트라인 상승)

            }          

        }

        cout << cnt << '\n';

        cnt = 1; // 다음 테스트를 위해 초기화

        v.clear(); // 다음 테스트를 위해 초기화

    }

    return 0;

}

 

4. 느낀점

나는 어떻게든 문제를 날로먹으려는 나쁜 습성이 있다.

 

지문을 잘 읽어야 한다고 문제를 풀때마다 생각하는데..

 

막상 문제를 접하면 뭔가 문제에 대해서 깊이있게 이해하고 싶어하지 않는(?) 그런 느낌이다.

 

이 문제도 역시 숫자가 높은 사람이 좋은 성적을 받은 건 줄 알고 한참 헤맸다.

 

알고보니 주어진 건 순위였고 숫자가 낮은 사람이 더 좋은 성적을 받은 것이었다.

 

그리고 한가지 더 헤멘 부분이 있다.

 

기준이 되는 면접 점수(최고 면접순위)를 temp로 설정했는데,

 

커트라인(temp)이 자꾸 올라가야 하는데(상위 순위자 보다 높은 면접 성적을 받아야 최종 합격 할 수 있으니까)

 

자꾸 내려가야 한다고 반대로 생각했었다.(즉 숫자가 작아져야 한다, 작은 숫자(순위) == 높은 점수)

 

문제를 잘 읽자! 그리고 내 생각에 틀린부분이 없는지 꼼꼼하게 검증하자!

 

아 그리고 이 문제는 그리디 알고리즘을 활용한 문제이다.

 

각 단계(해당 순위의 지원자)에서 최선의 선택(cnt)을 하기 때문이다.

 

오늘 하루도 쌓였다!