[Greedy/그리디] 백준 1946 신입 사원 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1946번: 신입 사원

 

 

 

2. 문제 풀이

선발 규칙: 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

 다소 문제에서 '선발 규칙'이 어렵게 써져 있습니다. 선발 규칙만 이해하면 쉽게 해결할 수 있습니다.

 

선발 규칙: 서류나 면접 중 1등은 합격. 그 외는 합격자의 서류나 면접 성적 중 1가지만 높아도 선발.

 쉽게 정리하면, 위와 같이 규칙을 쓸 수 있습니다. 만약 서류와 면접을 동시에 1등을 한 참가자가 있으면, 해당 채용에선 그 1명만 합격입니다. (ㄷㄷ...)

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 테스트케이스
T = int(input())
for _ in range(T):
    # 입력
    N = int(input())
    applicant = []
    for _ in range(N):
        applicant.append(list(map(int, input().split())))

    # 정렬(서류 기준 오름차순)
    applicant.sort()
    cut_line = applicant[0][1]  # 서류 1등의 면접 등수

    cnt = 1  # 합격자 수
    for i in applicant:
        # 서류는 앞 사람보다 낮지만, 면접 등수는 높은 참가자는 합격
        if cut_line > i[1]:
            cnt += 1
            cut_line = i[1]
    print(cnt)

 서류를 기준으로 오름차순 정렬합니다. 점수가 아니라, 등수이므로 낮을수록 높습니다.

 그 다음, 서류 1등의 면접 등수보다 높은 사람이 있으면 채용합니다. 그리고 해당 지원자의 면접 등수로 커트라인을 올립니다. 서류를 기준으로 오름차순 정렬되어 있으므로, 채용이 되려면 무조건 이전 합격자보다 '면접 등수'가 높아야 합니다.