[백준/C++] 1946번: 신입 사원

문제

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

---

문제 요약

회사에서 신규 사원 채용을 실시한다.

 

선발 시험은 1차 서류 심사와 2차 면접 시험으로 이루어진다.

 

서류 심사 성적과 면접 시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다.

 

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

 

이 때, 선발할 수 있는 신입 사원의 최대 인원 수를 출력한다.

---

코드

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

using namespace std;

int t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> t;

	while (t--) {
		int n;
		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));
		}

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

		// 현재까지 면접시험 최고 등수
		int min = v[0].second;

		int cnt = 1;

		for (int i = 1; i < v.size(); i++) {

			if (v[i].second < min) {
				min = v[i].second;
				cnt++;
			}
		}

		cout << cnt << "\n";

	}

	return 0;
}

---

코드 설명

1. 각 지원자의 서류 심사 순위와 면접 심사 순위를 벡터 v에 입력 받는다.

 

2. 서류 심사 순위를 기준으로 오름차순 정렬한다.

 

3. 가장 높은 서류 심사 순위의 지원자부터 차례로 접근하여, 현재까지 등장한 면접 시험 최고 등수보다 높은 등수의 지원자 수를 찾는다.

 

현재 탐색 중인 지원자의 면접 심사 순위가 이전까지 지원자들의 최고 면접 심사 순위보다 낮으면,

자신의 서류 심사 순위와 면접 심사 순위 둘 다 높은 지원자가 존재하므로 불합격이다.

 

현재 탐색 중인 지원자의 면접 심사 순위가 이전까지 지원자들의 최고 면접 심사 순위보다 높으면,

자신의 서류 심사 순위보다 높은 지원자들보다 면접 심사 순위가 더 높으므로 합격이다.

---

고찰

정렬을 이용한 그리디 알고리즘이다.

 

그리디 문제를 많이 접해보지 못해서인지 풀이 방법이 쉽게 떠오르지 않았다.

 

또, 계속해서 특정 알고리즘을 이용할 거라고 추측을 하게 되는데, 좋지 않은 습관인거 같다.