5주차(그리디) - [C++]백준1946 신입 사원

31 Mar 2022 in Study on Algorithm

백준1946 신입 사원 링크

문제

예제 입력

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int T, N;
vector<pair<int, int>> ranking;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> T;
    for (int i = 0; i < T; i++) {
        int ans = 1;
        cin >> N;
        ranking.clear();
        int a, b;
        for (int j = 0; j < N; j++) {
            cin >> a >> b;
            ranking.push_back({ a, b });
        }

        sort(ranking.begin(), ranking.end());
        int check = ranking[0].second; // 1차 1위의 2차성적

        for (int j = 1; j < N; j++) {
            if (ranking[j].second < check) {
                check = ranking[j].second;
                ans++;
            }
        }
        cout << ans << "\n";
    }
}

설명

이 문제는 신입 사원을 채용하기 위해서 1차와 2차 심사를 하는데 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세워 채용하는 최대 인원수을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 각 지원자의 심사 성적을 입력 받아 1차 심사 기준으로 정렬하여 1차 심사 2위는 2차 심사를 1위보다 잘 보면 채용이 되고 3위는 2차 심사를 2위보다 잘 보면 채용이 되는 방식으로 각 상황에서 선택하여 답을 구합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과