BOJ 1946 - 신입 사원(C++)

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

1946번: 신입 사원

서류와 면접 두 가지가 다른 지원자에 비해 떨어진다면 탈락

단순히 두 가지 조건에 대해 완전 탐색을 이용하기에는 시간초과가 발생, 최대한 탐색의 횟수를 줄이기 위해 고민했음

 

풀이

탐색하는 횟수를 줄이기 위해 우선 한가지 항목(서류 등수)에 대해 오름차순 정렬하여 탐색

다음 지원자(i+1)의 면접등수가 현재(i)의 지원자의 면접 등수보다 크다면 (i+1)순번의 지원자는 (i)지원자에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다는 의미이기 때문에 선발되지 않는다.

* 위의 등수가 크다는 말은 순위의 숫자가 더 크다는 의미 (ex) 1등<2등)

 

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

using namespace std;

vector<pair<int, int>> v;

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;

		v.clear();
		int y, x;
		for (int i = 0; i < N; i++) {
			cin >> y >> x;
			v.push_back(make_pair(y, x));
		}
		sort(v.begin(), v.end());
        
		int res = 1;
		int inter_score = v[0].second;
		for (int i = 1; i < v.size(); i++) {
			if (v[i].second < inter_score) {
				res++;
				inter_score = v[i].second;
			}
		}
		cout << res << endl;
	}
	return 0;
}