[Python] 백준 1946번 : 신입 사원

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

1946번: 신입 사원

---

 문제 풀이

정렬 문제인 줄 알고 풀었는데 그리디 문제이다.

 

우선 문제 이해를 잘해야 한다.

1차 2차 합쳐 모두 자신보다 나은 사람이 있다면 그 사람은 절대 뽑히지 못한다.

예를 들어, A는 2등 5등을 하고 B가 3등 6등을 하면 절대 B는 뽑히지 못한다는 것이다.

바로 예상할 수 있는 것은 1차 1등과 2차 1등이 동일 인물이 아니라면 

무조건 2명 이상이라는 것이다.

 

정렬하여 1차의 1등을 기준으로 잡았을 때, 합격하기 위해서는 1등의 2차 등수보다 높아야 한다.

기준보다 등수가 높으면 기준을 바꾸어주고 합격자 수를 +1 해준다.

 느낀 점

아이디어 하나를 못 찾아서 생각보다 오래 걸린 문제이다. 그리고 그리디 문제일 줄이야.. 

 코드

import sys
        
T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()

    cnt = 1
    max_ = arr[0][1]
    for i in range(1,N):
        if max_ > arr[i][1]:
            cnt += 1
            max_ = arr[i][1]
            
    print(cnt)