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

 

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

using namespace std;

int main(void)
{
	int test=0;
	cin>>test;
	
	for(int i=0; i<test; i++)
	{
		int a=0;
		cin>>a;
		vector<pair<int,int> > V;
		for(int i=0; i<a; i++)
		{
			int num1=0;
			int num2=0;
			cin>>num1>>num2;
			
			V.push_back(make_pair(num1,num2));
		}
		sort(V.begin(), V.end());
		
		int count=1;
		int min=V[0].second;
		for(int i=1; i<V.size(); i++)
		{
			if(V[i].second<=min)
			{
				count++;
				min=V[i].second;
			}
		}
		cout<<count<<endl;
	}
	
	
	return 0;
}

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 서 류심사 성적, 면접시험 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.

 

즉 서류심사 성적이나 면접시험 성적의 순위가 하나라도 다른 지원자보다 떨어지면 선발되지 않는다.

그러면 어떻게 문제를 해결하여야 하는가??

일단 서류심사 성적 순으로 정렬을 한다. 정렬을 하고 나면 서류심사 성적 1등인 사람이 있을 것이다. 이 사람의 면접시험  성적을 min 값으로 잡고 다른 지원자와 비교해 본다. 다른 지원자의 면접시험 성적은 min값과 같거나 혹은  커야지 선발이 가능하다.

 

예를 들어 정렬을 하고 나면 

1 6

2 9

3 5

4 3

이렇게 된다고 치자.(편의상 순서대로 1,2,3,4 지원자로 보겠다.)

 

2번째 지원자를 보겠다. 선발되기 위해서는 일단 서류심사 성적은 1번 지원자보다 낮기 때문에 면접시험 성적은 1번 지원자보다 높아야한다. 그런데 보면 1번 지원자는 6 2번 지원자는 9이다. 둘다 1번 지원자보다 낮기 때문에 선발되지 않는다.

3번 지원자를 보면 서류심사 성적은 당연히 1번보다 낮고 면접시험 성적은 1번보다 높은 것을 확인할 수 있다. 이제 min값이 3번 지원자의 면접시험 성적으로 갱신된다. 위 과정을 반복하면 선발되는 인원을 알 수 있다.

 

만약 min값을 두지 않고 이중 for문을 사용하여 문제를 해결하려고 시도하면 시간초과가 발생할 수 있으니 주의하자.