BOJ : 1946 신입 사원

 

---

[BOJ1946 리뷰]

오랜만에 푼 그리디 문제이다.

문제 조건을 잘 풀어보면 다음과 같다.

• 신입사원으로 선발 되려면 다른 지원자보다 최소한 점수 하나가 더 높아야 한다.
• 즉, 점수가 둘다 낮으면 선발될 수 없다.

문제를 해결하기 위해서 먼저 첫번째 기준으로 정렬을 하자. (두번째 기준으로 정렬을 해도 상관이 없다.)
정렬이 되면 서류성적순으로 1등부터 꼴등까지 쭉 정렬이 될 것이다.

이제 여기서 문제의 핵심을 잘 생각해보면 된다. 신입사원으로 선발이 되기 위해서는 최소한 점수 하나가 더 높아야 한다.
지금은 서류성적 순으로 정렬이 되어있기 때문에, 그 밑에 있는 사원들은 일단 서류성적은 첫번째 지원자보다 무조건 낮을 수 밖에 없다. 그렇기에 이 사람이 선발이 되기 위해서는 면접 점수가 무조건 높아야 한다.

이 조건을 생각하면서 지원자 한명씩 추려보면 된다.

3 2
1 4
4 1
2 3
5 5

이 예시에서 서류성적 순으로 정렬을 하면 다음과 같다.

1 4
2 3
3 2
4 1
5 5

서류성적 1등의 면접등수는 4등이다.
이제 다음 지원자들을 하나씩 보면서 면접등수를 비교해보면 된다.
다음 지원자들의 서류성적은 무조건 낮으므로 면접등수가 만약 더 낮다면 절대 선발될 수 없다.

두번째 지원자를 보니 면접점수가 3등으로 첫번째 지원자의 면접성적보다 높으므로 선발될 수 있다.
이제 두번째 지원자의 면접등수로 기준을 바꾸면 된다.
세번째 이후 지원자들 역시 두번째 지원자보다 서류성적이 낮기 때문이다.

이런식으로 지원자 한명씩 보며 면접등수가 더 높은 지원자들만 선택하여 계산하면 된다.

'''
    2021.07.31
    BOJ : 1946 신입 사원 (https://www.acmicpc.net/problem/1946)
    Algorithm : 그리디
'''
T = int(input())
for _ in range(T) :
    list = []
    N = int(input())
    for _ in range(N) :
        a, b = map(int,input().split())
        list.append([a,b])
    list.sort(key = lambda x : x[0])
    ans = 0
    score = int(1e9)
    for cur in list :
        if cur[1] < score :
            ans += 1
            score = cur[1]
    print(ans)