신입사원 #1946 c++ 풀이

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

1946번: 신입 사원

 

 

dp를 어느정도 감을잡고 greedy를 푸는 중이다.

 

1 4

2 3

3 2

4 1

5 5 

로 sort후, 뽑힌 사람들을 확인하니 두번째 요소에 대해 내림차순인 것들만 count 해주면 된다.

솔직히 이게 왜 greedy인지 모르겠다.

 

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

using namespace std;

int main() {


	int T;
	cin >> T;
	vector<pair<int, int>> v;
	while (T--) {
		int n;
		cin >> n;
		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 cnt = 1;
		int k = v[0].second;
		for (int i = 0; i < v.size()-1; i++) {
			if (k > v[i + 1].second) {
				k = v[i + 1].second;
				cnt++;
			}
		}
		cout << cnt << endl;
		v.clear();
	}

	return 0;
}