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

문제

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

 

문제 내용

선발할 수 있는 신입사원의 최대 인원수를 출력하는 문제이다.

이때 선발 조건은 서류 또는 면접 심사 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 것이다.

즉, 서류와 면접 심사가 남들보다 모두 뒤처진다면 탈락하게 된다.

 

문제 풀이

서류와 면접 점수를 pair로 입력받는다.

그리고 일단 서류 점수로 정렬을 한다. 

pair로 이뤄진 배열에 sort()를 쓰면 첫 번째 인자(서류 점수)의 순서대로 정렬이 된다.

 

이제 우리는 두번째 인자(면접 점수)를 비교하면 된다.

우리가 지금 판단하고자 하는 사람을 A라고 하면, A보다 서류 점수가 높은 면접자들보다 A의 면접 점수가 좋아야 한다.

(면접 점수는 작을수록 좋다. 입력받은 것이 등수니까)

즉, 정렬된 배열에서 자신의 앞에 있는 사람들의 면접 "등수" 중 가장 좋은 "등수"와 비교했을 때, 자신의 "등수"가 가장 좋아야 한다. (숫자가 작아야 한다)

 

이 부분을 반복문을 통해 풀었다.

만약 앞사람들의 면접 등수 중 가장 높은 등수(sc) 보다 자신의 면접 점수가 좋으면 (자신의 숫자가 더 낮으면), sc의 값을 갱신해야 한다.

sc보다 자신의 면접 점수보다 나쁘면 (자신의 숫자가 더 크면), count값을 증가시킨다.

이는 내가 탈락한다는 의미이다.

 

count의 값이 탈락자의 수이므로, 우리가 출력을 할 때에는 전체 인원 수에서 이 값을 빼주어야 한다.

 

코드

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


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int testcase;
	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		int num,a,b; cin >> num;
		vector<pair<int, int>>score;
		for (int j = 0; j < num; j++) {
			cin >> a >> b;
			score.push_back(make_pair(a, b));
		}

		//문제 해결
		sort(score.begin(), score.end()); //서류 점수로 정렬

		int sc = score[0].second;
		int count = 0;
		for (int j = 1; j < num; j++) {
			if (sc <= score[j].second) count++;
			else sc = score[j].second;
		}

		//결과 출력
		cout << num-count << '\n';
	}
}