[python] 백준 1946 신입사원

문제 링크

www.acmicpc.net/problem/1946

1946번: 신입 사원

문제 설명

즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

요약을 하자면 저 한 문장으로 대체 가능합니다.

또한 성적이 일반 점수가 아니라 순위이기 때문에 낮을수록 좋습니다.

일반적으로 생각하는 이중 포문으로 푼다면 시간 초과가 뜨기 때문에 '그리디' 스럽게 풀어내야 합니다.

 

접근 방법

처음에는 수식으로 풀 수 있을지도 모른다고 생각했습니다.

입출력에서도 나오는 두 번째 테스트 케이스에서 자꾸 걸렸기에 포기했습니다.

 

그다음으로 떠올린 방법은 한쪽을 fix 해버리는 방법입니다.

저는 서류 심사 결과를 기준으로 정렬을 시키고 그 다음에 얘네들이 min 값 보다 작은지 비교했습니다.

서류 심사 값이 큰 지원자가 합격을 할 수 있는 방법은 면접 성적만큼은 다른 사람들보다 작아야 합니다.

따라서 면접의 결과만을 비교하는 방식으로 해결했습니다. 

 

소스 코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    a = []
    cnt = 1
    for k in range(n):
        a.append(list(map(int,input().split())))
    a.sort()
    m = a[0][1]
    for i in range(1,n):
        if a[i][1] < m:
            m = a[i][1]
            cnt+=1
    print(cnt)