[Python] boj no. 1946 : 신입 사원

Problem

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

Idea

선발자가 되기 위해서는 다른 선발자들에 대해 서류심사 혹은 면접시험 순위가 높아야 한다.

해결방법을 찾기 위해 두 가지 기준을 만들었다.

서류심사 혹은 면접시험 순위가 1위인 후보자는 항상 선발자가 된다. 다른 후보자들은 먼저 선발된 후보자들과 서류심사 혹은 면접시험 성적을 비교하여 한 쪽이라도 순위가 높을 경우 선발자에 포함한다. 우선 서류심사 순위을 오름차순으로 하여 후보자들을 정렬했다. 정렬하게 되면 0번째의 후보자는 무조건 선발자가 되고, 그 다음의 후보자들부터는 면접시험 순위를 앞의 선발자들과 비교하여 더 높을 경우에만 선발자에 포함한다. 서류심사 순위가 오름차순이기 때문에 뒷 순번의 후보자들은 서류심사 성적으로는 앞 순번 후보자들을 제칠 수 없기 때문이다.

따라서, 선발자를 뽑을 때마다 면접시험 순위의 커트라인을 최신화한다.

Code

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    applicant = [tuple(map(int, input().split())) for _ in range(N)]
    applicant.sort()
    sol = 1
    threshold = applicant[0][1]
    for a in applicant[1:]:
        if a[1] < threshold:
            threshold = a[1]
            sol += 1
            
    print(sol)

Comment