백준 1946번(그리디)

백준 1946번(그리디)

정말 어려웠습니다. 문제에 써있는 최댓값이라는 단어 때문에 더욱 어렵게 생각했던 것 같습니다. 사실 어차피 전체 인원에서 비교해야하기에 각 순위를 비교하는 순서만 잘 고려하면 잘 풀리는 문제였습니다. 일단 두 성적 중 첫번째로 주어지는 것을 first, 두 번째는 second 라고 할 경우 first를 기준으로 오름차순으로 정렬합니다. 이렇게 할경우 이제 위에서 아래로 비교를 시작합니다. 그렇게 하면 어차피 first값은 아래로 내려갈 수록 순위는 밀려나기에 뽑히려면 second의 순위라도 높아야합니다. 그리고 방금 뽑힌 사람보다 아래에 있는 사람은 방금 뽑힌 사람의 second 순위 보다 높아야합니다. 이런 아이디어로 비교를 진행해나가며 사람을 뽑을 때마다 count를 하나씩 증가시켜주면 문제를 해결할 수 있습니다.

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

using namespace std;

int main() {
	int t;
	int n;
	int a;
	int b;
	int min;
	int count = 0;
	vector<pair<int, int>> v;

	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> a;
			cin >> b;
			v.push_back(pair<int, int>(a, b));
		}

		sort(v.begin(), v.end()); // 따로 compare 정의 안해줄 경우 pair의 first값 기준으로 오름차순으로 정렬

		min = v[0].second;
		count++;

		for (int j = 0; j < v.size(); j++) {
			if (v[j].second < min) {
				min = v[j].second;
				count ++;
			}
		}

		cout << count << endl;
		count = 0;
		v.clear();
	}


	return 0;
}