BOJ 1946 신입 사원

문제에서 '최고만을 지향하는' 이라는 힌트를 통해 그리디(Greedy) 알고리즘을 사용하는 것을 유추할 수 있다.

따라서 서류심사 성적, 면접 성적 순위중 하나를 잡아 1등부터 나열한후 첫번째 부터 선택을 해 나간다. 예를 들어 서류 심사 기준으로 정렬했다고 가정해보자. 테스트 케이스를 정렬하였을 경우 각각 다음과 같이 된다.

a b //a=서류 b=면접
1 4
2 3
3 2
4 1
5 5

a b //a=서류 b=면접
1 4
2 5
3 6
4 2
5 7
6 1
7 3

이미 서류 기준으로 정렬 하였기 때문에 A지원자 (1 4) 와 B지원자 (2 3) 을 비교하면 B지원자는 무조건 A지원자의 면접 순위보다 높아야 합격 할 수 있다. 즉 위의 정렬한 예시에서는 이후 지원자가 이전 지원자의 면접 최고 순위 보다 높아야 한다.  풀이는 다음과 같다.

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

bool compare(pair<int,int> a, pair<int,int> b)
{
	return a.first < b.first;
}

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

	int T;
	cin >> T;

	for(int i = 0; i < T; i++)
	{
		int n;
		vector<pair<int, int>> test;

		cin >> n;

		for(int j = 0; j < n; j++)
		{
			int a, b; // a= 서류, b= 면접
			cin >> a >> b;
			test.push_back({ a,b });
		}

		sort(test.begin(), test.end(), compare);
		
		int cnt = 0;
		int max = 100001;
		for(int j=0;j<test.size();j++)
		{
			if(test[j].second < max)
			{
				max = test[j].second;
				cnt++;
			}
		}
		cout << cnt<<"\n";
	}
}