백준 - 신입 사원 (1946) [C++]

 이 문제는 그리디를 이용해서 푸는 문제이다. 매 테스트 케이스마다 최대 100000만의 입력이 주어지므로, O(n) 이하의 알고리즘으로 풀어내야 한다. 즉, O(n^2) 알고리즘으로는 절대 풀 수 없다. 그래서 그리디를 떠올렸고, 처음에는 서류 기준으로 정렬해서 최고의 점수를 낸 사람의 두 점수를 기준으로 한번 거르고, 그 다음에는 면접 기준으로 걸러서 정답을 제출했는데 틀렸다. 결국 도저히 안 풀려서 검색을 통해 도움을 받았다.

 

 내가 간과한 것은 최고의 점수를 낸 사람의 기준으로만 탐색을 돌렸다는 것이다. 그럴 필요 없이 한 가지에 대해 정렬하면 일단 그 기준에 대해서는 첫번째 인덱스를 제외하고는 전부 탈락 위기라는 것이다. 이 때 다른 한 가지 기준을 만족하는지 보고, 만족할 경우 그 값으로 최고 점수를 갱신하면 더 정확하게 나올 수 있을 것이다. 이 생각을 하지 못한게 아쉬웠다.

 

 한 가지 주의할 점은 문제에 주어진 숫자들은 순위이지 점수가 아니라는 것이다. 이것 때문에 문제 이해에만 30분을 썼다..

 

 

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

using namespace std;

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

	int T;

	cin >> T;

	for (int test = 0; test < T; test++) {
		int N;
		cin >> N;
		vector<pair<int, int>> lists;

		for (int i = 0; i < N; i++) {
			int paper, speaking;
			cin >> paper >> speaking;
			lists.push_back({ paper, speaking });
		}

		if (lists.size() == 1) {
			cout << 1 << '\n';
			continue;
		}

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

		int best = lists[0].second;
		int answer = 0;

		for (int i = 0; i < N; i++) {
			if (lists[i].second <= best) {
				answer++;
				best = lists[i].second;
			}
		}

		cout << answer << '\n';
	}

	return 0;
}