[백준 1946] 신입 사원

문제설명

알고리즘

1. 입력 값 저장

2. 서류 점수 기준으로 오름차순 정렬

3. 서류 1등의 면접 점수를 기준으로 다음 사람들의 면접 점수를 조회해 더 높은 값이 나올때 마다 합격, 및 업데이트

코드

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

vector<pair<int, int>> grade;


int main() {
	int T, N;
	cin >> T;

	while (T) {
		cin >> N;
		for (int i = 0; i < N; i++)//점수 입력
		{
			int x, y; 
			cin >> x >> y; 
			grade.push_back({x,y});
		}
				
		sort(grade.begin(), grade.end()); //서류 기준 오름차순 정렬
		int cnt = 1;// 1등은 합격
		int interview = grade[0].second;//1등의 면접 점수
		for (int i = 0; i < grade.size(); i++)//면접 점수확인 
		{
			int y = grade[i].second;//면접 점수
			if (y < interview) {//통과한 사람의 면접 점수보다 더 좋으면 합격
				interview = y;//면접 점수 업데이트 
				cnt++;
			}
		}
		cout << cnt<<'\n'; 
		grade.clear();
		T--;
	}
}

고찰

이 문제는 처음에 읽었을 때 이해가 잘 안되었다

처음에는 인원 수의 절반만 넘은 등수를 가졌으면 합격이 되는 줄 알았는데, 테스트 케이스에서 부터 틀렸다

 

중요한 점은, 남들보다 나은게 있어야지 선발이 된다는 것이었다

따라서 서류 점수를 높은 순으로 정렬하고, 처음 1등을 한 사람은 무조건 합격이다

그리고 그 사람의 면접 점수를 기준으로 이보다 더 나은 사람이 나와야 남들보다 나은게 있다고 판단해 합격을 하는것이다

면접 점수가 더 나은 사람이 나올 때 마다 업데이트를 해서 비교 해준다

이때 서류점수는 정렬이 되어있음으로 써 비교를 할 필요가 없다

왜냐하면 점수를 한 사람씩 조회할 때 마다, 전사람 보다는 서류 점수가 낮은 사람이니 면접이 높아야만 합격이 되는 것이다