문제접근
•
다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙
•
서류심사 성적이든 면접심사 성적이든 둘 중 1등인 사람은 무조건 다른 지원자보다 우수한 성적이기 때문에 선발이 보장
•
서류심사 성적을 기준으로 정렬을 해주게 되면 서류심사의 1등을 찾을 수 있게 되고 그 다음 선발의 기준은 서류심사 1등 선발자의 면접시험 등수보다 더 나은 사람이면 된다.
•
여기서 주의할점은 서류심사 1등의 면접심사 등수가 계속 다음 선발의 기준이 되는 것이 아니라는 점이다.
서류심사 1등의 서류등수로 다음 선발자를 찾게 되면 그 다음 선발의 기준은 이전 선발자의 면접심사 등수보다 더 나아야 한다.
그렇지 않으면 기존 원칙에 위반이 되는 상황이 벌어짐(아래 예시 참고)
•
예시로 확인을 해보자
1번 지원자 : 3 6
2번 지원자 : 7 3
3번 지원자 : 4 2
4번 지원자 : 1 4
5번 지원자 : 5 7
6번 지원자 : 2 5
7번 지원자 : 6 1
-> 정렬 후
4번 지원자 : 1 4 //선발. 다음 선발의 기준은 면접 등수가 4등 보다 우수
6번 지원자 : 2 5 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
1번 지원자 : 3 6 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
3번 지원자 : 4 2 //선발. 선발기준인 면접 등수가 4등 보다 우수. 다음 선발의 기준은 면접 등수가 2등 보다 우수
5번 지원자 : 5 7 //미선발. 선발기준인 면접 등수가 2등 보다 떨어짐
7번 지원자 : 6 1 //선발. 선발기준인 면접 등수가 2등 보다 우수. 다음 선발의 기준은 면접 등수가 1등 보다 우수(없음)
2번 지원자 : 7 3 //미선발. 선발기준인 면접 등수가 1등 보다 떨어짐
Plain Text
복사
선발 기준이 계속 업데이트 되어야 하는 이유(업데이트 하지 않으면 ???)
4번 지원자 : 1 4 //선발. 다음 선발의 기준은 면접 등수가 4등 보다 우수
6번 지원자 : 2 5 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
1번 지원자 : 3 6 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
3번 지원자 : 4 2 //선발. 선발기준인 면접 등수가 4등 보다 우수. 선발 기준은 여전히 4등
5번 지원자 : 5 7 //미선발. 선발기준인 면접 등수가 4등 보다 떨어짐
7번 지원자 : 6 1 //선발. 선발기준인 면접 등수가 4등 보다 우수. 선발 기준은 여전히 4등
2번 지원자 : 7 3 //선발. 여기서 문제가 발생
이런식으로 업데이트를 하지 않으면 맨 마지막의 2번 지원자도 선발을 하게 된다.
그렇게 되면 2번 지원자의 경우 기존에 뽑힌 4번 지원자와 비교했을때는 면접심사 등수가 우수하여 원칙을 위배하지 않게 되지만, 기존에 뽑힌 나머지 두 지원자(3번, 7번)와 비교했을때는 원칙을 위배하게 된다.
놓쳤던 부분
•
합격할 수 있는 모든 신입사원들은 서로에 대해서 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 을 성립해야함.
1번 지원자 : 3 6
2번 지원자 : 7 3
3번 지원자 : 4 2
4번 지원자 : 1 4
5번 지원자 : 5 7
6번 지원자 : 2 5
7번 지원자 : 6 1
Plain Text
복사
◦
위와 같은 입력이 들어왔을때, 2번 지원자의 서류등수가 7등이기 때문에 7번 지원자를 제외한 모든 지원자가 선발될 수 있는 것이 아니다.
◦
예를 들어, 1번 지원자가 뽑히게 된다면 그 이후 뽑히는 지원자들의 점수는 서류등수가 3등 보다 우수하거나 면접등수가 6등 보다 우수해야한다.
코드
2800 KB
504 ms
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
int t;
int n;
std::vector<std::pair<int, int> > score;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
score.resize(n);
for (int i = 0; i < n; i++)
std::cin >> score[i].first >> score[i].second;
}
void solution()
{
int limit;
int count = 1;
sort(score.begin(),score.end());
limit = score[0].second;
for (int i = 1; i < n; i++)
{
if (limit > score[i].second)
{
++count;
limit = score[i].second;
}
}
std::cout << count << "\n";
}
int main(void)
{
input_setting();
std::cin >> t;
for (int i = 0; i < t; i++)
{
input();
solution();
}
return (0);
}
C++
복사
