❓문제 설명

문제 : 백준 1946 신입 사원
난이도 : 실버 1

문제 요약

• 신입 사원 채용 과정은 1차 서류 심사와 2차 면접 시험으로 이루어집니다.
• 최고의 인재를 뽑기위해 다른 모든 지원자들과 1차,2차 점수를 비교했을 때 두 시험 중 하나라도 다른 지원자보다 떨어지지 않는 자만 선발합니다.
• 이때, 최대로 뽑을 수 있는 신입 사원의 수를 구하면 됩니다.
• 테스트 케이스 T (1이상 20이하)
• 지원자의 수 N (1이상 10만 이하)
• N개 줄에는 각 지원자의 서류 심사 성적, 면접 성적의 순위가 공백을 사이에 두고 주어집니다.

🎯문제 해결 방법

먼저 저는 이 문제에서 주어진 내용을 잘못 이해하고 있었습니다.

테스트 케이스 마다 주어지는 지원자들의 정보입니다.
저는 저 숫자가 순위가 아닌 받은 점수라고 생각하고 풀어서 제출하면 다른 테스트 케이스에 걸러져서 틀렸던 겁니다...!

잘못이해하고 푼 코드를 설명하기보다는 바로 이 문제를 어떻게 해결해야하는지에 대해서 설명드리겠습니다.

이 문제는 그리디 알고리즘을 떠올려야합니다. 그때 그때 순간에 가장 좋은 선택지를 골라 신입 사원을 최대로 뽑도록 해야합니다.

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

• 지원자들의 1차 순위와 2차 순위를 입력 받습니다.

서류 순위	면접 순위
1	4
2	3
3	2
4	1
5	5

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

• 순위가 낮을수록 시험을 더 잘 본 것이기에 오름차순으로 정렬해줍니다. (ex. 1등 > 2등)

int tmp = 0; // 기준이 되는 비교 대상
ret = 1; // 현재 뽑은 신입 사원의 수

• 1차 순위를 기준으로 정렬한 뒤 다른 모든 사람들보다 뛰어난 첫 번째에 있는 1등은 무조건 뽑히므로 현재 뽑은 신입 사원의 수를 1로 두고 시작합니다.
• tmp에는 1등의 위치인 index 0을 담습니다.

for(int i=1; i<n; i++){
	if(v[tmp].second > v[i].second){
		ret++;
		tmp = i;
	}
}

• 1등과 2등의 면접 순위를 비교합니다.
• 1등의 면접 순위보다 2등의 면접 순위가 더 높으면 뽑을 수 있기에 ret을 하나 더해준 뒤 다음 기준이 되는 면접 순위를 i로 둡니다.

서류 순위	면접 순위
1	4
2	3
3	2
4	1
5	5

• 표로 보면 이렇습니다. 1등의 면접 순위는 4위, 2등의 면접 순위는 3위 이므로 서류 1등이 뽑히고 다음으로 서류 2등이지만 1등보다 면접 순위가 높으므로 뽑히게 되는 것이죠.

서류 순위	면접 순위
1	4
2	3
3	2
4	1
5	5

• 다음으로는 서류 2등의 면접 순위와 서류 3등의 면접 순위를 비교합니다.
• 서류 3등이지만 면접 순위가 서류 2등보다 높으므로 뽑히게 됩니다.

이러한 과정을 반복하게 되면

서류 순위	면접 순위
1	4
2	5
3	6
4	2
5	7
6	1
7	3

이 예시에서는 (1,4), (4,2), (6,1) 지원자들이 뽑히게 됩니다.

💻전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int t,n;
int ret;
vector<pair<int,int>> v;

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while(t--){
		cin >> n;
		v.clear();
		for(int i=0; i<n; i++){
			int a,b;
			cin >> a >> b;
			v.push_back({a,b});
		}
		sort(v.begin(), v.end());
		
		int tmp = 0;
		ret = 1;
		for(int i=1; i<n; i++){
			if(v[tmp].second > v[i].second){
				ret++;
				tmp = i;
			}
		}
		cout << ret << '\n';
	}
	return 0;
}