Baekjoon 1946 신입 사원

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

소스결과 2888 KB / 144 ms

언어 C++ 17

출처 Baekjoon, ACM-ICPC 2006

분류 그리디 알고리즘

 

설명

한 지원자의 서류 심사 성적과, 면접시험 성적중 적어도 다른 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 하에 지원자를 선발할 때 선발 할 수 있는 최대 인원 수를 구하여라.

 

되게 간단한 듯 보이면서 많이 틀렸던 문제다.

서류 심사 성적을 기준으로 정렬을 한 뒤, 면접 시험에 대해서 처리 하는 부분이 애매했었다.

결과론적으로 서류 심사 성적이 같다면 면접 시험 성적이 좋은 사람을 위로 놓았다.

또한 서류심사 성적이 낮지만, 면접 시험 성적이 가장 좋은 경우도 존재 할 수 있기 때문에, 정렬된 값을 순차적으로 탐색 할 때, 면접 시험 성적 커트라인을 계속 갱신해주었다.

 

알고리즘

1. 지원자의 성적을 서류 심사 성적을 기준으로 정렬한다. 단 서류 심사 정석이 같은 경우 면접 시험 성적이 좋은 경우를 더 좋은 경우로 판단한다.

2. 0번 인덱스부터 모든 경우의 수를 판단하며, 서류 성적이 같은 경우 합격 처리하며, 면접 점수 커트라인을 갱신한다.

3. 선발 인원 수를 출력한다.

 

소스코드

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

using namespace std;

struct TestScore {
	int first;
	int second;

	TestScore() {};
	TestScore(int first, int second) : first(first), second(second) {}
};

bool compare(TestScore& ts1, TestScore& ts2) {
	if (ts1.first < ts2.first)
		return true;
	else if (ts1.first == ts2.first) {
		if (ts1.second <= ts2.second)
			return true;
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int tcc;
	cin >> tcc;

	for (int tc = 0; tc < tcc; tc++) {
		vector<TestScore> tsv;
		int n;
		int res = 1;

		cin >> n;
		tsv.resize(n);

		for (int i = 0; i < n; i++)
			cin >> tsv[i].first >> tsv[i].second;

		sort(tsv.begin(), tsv.end(), compare);

		int secondMin = tsv[0].second;

		for (int i = 1; i < n; i++) {
			if (tsv[i].first == tsv[i-1].first) {
				res++;
				if (secondMin > tsv[i].second)
					secondMin = tsv[i].second;
			}
			else
			{
				if (secondMin > tsv[i].second) {
					res++;
					secondMin = tsv[i].second;
				}
			}
		}

		cout << res << '\n';
	}

	return 0;
}