[백준] No.1946 - 신입사원 (C++)

문제

 

www.acmicpc.net/problem/1946

1946번: 신입 사원

 

풀이

 

solved.ac 난이도: Silver1

 

이전에 풀었던 회의실 배정 문제와 유사한 그리디 문제.

 

일단 입력의 크기가 N(1 ≤ N ≤ 100,000)로 굉장히 크기 때문에 O(N^2) 시간복잡도를 가지는 알고리즘으로 해결하긴 힘들다.

따라서 아래와 같은 그리디 방식으로 접근하자.

 

일단 서류심사의 기준으로 pair<int,int> 배열을 정렬하자.

예제가 입력이 아래와 같이 주어지면

3 6

7 3

4 2

1 4

5 7

2 5

6 1

 

결과는 다음과 같다.

1 4

2 5

3 6

4 2

5 7

6 1

7 3

 

일단 이 정렬에서는 자신(idx)은 아래의 값들보다 서류 심사 순위는 높다는 것을 알 수 있다.

따라서 자신의 면접 성적 순위가 위의 값들 중에서 더 높은 값이 있다면 자신은 선발될 수 있다.

 

그러므로 위에서부터 내려가며, 자신이 면접 성적 순위의 최솟값(min_ranking)보다 더 높다면 카운트를 하고 해당 값으로 min_ranking을 업데이트하자.

여기서 min_ranking를 업데이트 하는 이유는 아래의 값들은 모두 자신보단 심사 순위가 낮기 때문에 적어도 면접 성적 순위는 min_ranking보다 높아야 선발될 수 있기 때문이다.

 

예제의 결과는 아래와 같다.

1 4 -> min_ranking: 4

2 5 -> min_ranking: 4

3 6 -> min_ranking: 4

4 2 -> min_ranking: 2

5 7 -> min_ranking: 2

6 1 -> min_ranking: 1

7 3 -> min_ranking: 1

 

코드