[C++] 백준 1946: 신입 사원

문제

[C++] 백준 1946: 신입 사원 SILVER 1
https://www.acmicpc.net/problem/1946

 

---

 

접근 방법

이 문제는 지원자들의 서류 성적, 면접 성적이 주어졌을 때,
“두 성적 모두 다른 지원자에게 밀리는 경우 탈락”이라는 기준으로 합격할 수 있는 최대 인원 수를 구하는 문제다.

 

처음에는 각 지원자에 대해 “이 사람보다 서류, 면접 둘 다 더 좋은 사람이 있는지”를 2중 for문으로 전부 비교하는 방식으로 생각했다. 하지만 이렇게 하면 지원자 수 N이 클 때 O(N²) 가 되어 시간 초과가 발생했다..

 

그래서 접근을 바꿔서,

1. 서류 성적 기준으로 오름차순 정렬을 하고
2. 서류 1등은 무조건 합격이므로 기준으로 삼고,
3. 뒤에서부터는 지금까지 본 면접 성적의 최솟값(Min)을 계속 갱신하면서,
4. 현재 지원자의 면접 성적이 Min보다 더 좋으면(작은 등수면)
   → 이 사람은 “앞에 있는 누구에게도 면접에서 밀리지 않음”
   → 합격 인원에 포함

이라는 방식의 그리디 알고리즘으로 해결했다.

정렬 후에는 서류 성적이 이미 “겹치지 않고 정렬된 상태”이기 때문에,
면접 성적만 비교하면서 Min을 갱신해 주면
2중 for문 없이도 합격 가능 인원을 정확히 셀 수 있다.

 

구현 시 주의할 점

• 서류 1등은 무조건 뽑히므로, 이렇게 초기화한다.

int cnt = 1;
int Min = score[0].second; // 면접 성적 최솟값(=등수 기준)

• 그 다음 사람부터는 아래처럼 기존 Min보다 더 좋은 면접 등수인 경우에만 합격 인원을 늘리고 Min을 갱신한다.
  • 여기서 “Min보다 작다”는 건
    지금까지 나온 사람들 중 면접 성적이 가장 좋은 사람이라는 뜻이다.
  • 정렬 덕분에 서류에서는 이미 뒤에 있는 사람에게 밀리기 때문에,
    면접이라도 더 잘 본 경우에만 “둘 다 안 밀리는” 조건을 만족하게 된다.

if (score[i].second < Min) {
    Min = score[i].second;
    cnt++;
}

 

---

 

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case = 0;
	cin >> test_case;
	for (int i = 0; i < test_case; i++)
	{
		int n = 0;
		cin >> n;

		vector<pair<int, int>> score(n);
		for (int i = 0; i < n; i++)
			cin >> score[i].first >> score[i].second;

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

		int cnt = 1, Min = score[0].second;
		for (int i = 1; i < n; i++)
		{
			if (score[i].second < Min)
			{
				Min = score[i].second;
				cnt++;
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}