[C++] BOJ(백준) 1946 신입 사원

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

1946번: 신입 사원

 

그리디 문제다.

 

두 사람의 두 점수를 비교 했을 때 한 점수는 낮고 한 점수는 높아야 한다.

두 등수 중 하나를 기준으로 정렬하고 다른 등수가 전 사람보다 높은지 판별하면 된다.

 

등수는 중복되지 않으니 정렬을 사용하지 않고 하나의 등수를 인덱스로 사용해도 된다.

 

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

pair<int, int> arr[100000];

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T, N;

	cin >> T;

	while (T--) {
		cin >> N;
		for (int i = 0; i < N; i++) 
			cin >> arr[i].first >> arr[i].second;

		// 서류 점수를 기준으로 정렬
		sort(arr, arr + N);

		int myeonJub = arr[0].second;
		int cnt = 1;

		for (int i = 1; i < N; i++) 
			// 정렬 했으므로 서류 점수는 증가하고 면접 점수는 감소해야 함
			if (arr[i].second < myeonJub) {
				cnt++;
				myeonJub = arr[i].second;
			}

		cout << cnt << "\n";
	}
}

 

정렬 대신 인덱스를 이용한다면 시간과 메모리가 단축될 것 같다.

 

---

작성하다가 생긴 의문점이 있다.

1
6
1 1
2 6
3 5
4 4
5 3
6 2

위의 예제는 5명이 합격할 수 있지 않나? 로직대로면 정렬이든 인덱스든 1이 나온다.

찾지 못한 오류가 있을 것 같은데 모르겠다 ^!^