[백준 1946] 신입 사원

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

---

해설

이번 문제는 그리디 알고리즘을 사용하는 문제이다.

 

문제에서 중요한 문장은

 

"두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다."

이 부분이었던 거 같다.

 

일단, 이 문제를 보고 헷갈릴 수 있는 데, "각각의 지원자의 서류심사 성적, 면접 성적의 순위" 

이 문장만 보고는 서류 심사 성적이랑 면접 성적 순위가 주어지겠구나 라고 오해할 수있다.

 

입력에서는 서류 심사 성적 순위와 면접 성적 순위가 주어진다.

 

난 이 문제를 풀 때

 

i) 서류 심사 성적으로 정렬

ii) 동석차가 없으니 0번 배열은 무조건 합격이라서 cnt를 1로 세팅 해놓았다.

iii) 그 다음 for문을 1번 배열부터 돌려 자신의 면접 성적 순위가 vp[i-1]보다 높으면 cnt 1 증가시켰다.

(조심해야할 점은 vp[i].second를 save에다가 갱신해줘야 하는 데, 아래 소스코드를 참고하길 바란다.)

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<pair<int, int > > vp;
		for(int i=0; i<n; i++){
			int a, b; cin >> a >> b;
			vp.push_back(make_pair(a,b)); 
		}
		sort(vp.begin(), vp.end());
		int cnt = 1;
		int save = vp[0].second;
		for(int i=1; i<n; i++)
			if(save > vp[i].second){ 
			cnt++;
			save = vp[i].second;
			}
		cout << cnt << '\n';
	}
}