[예제] [파이썬] [그리디] 씨름 선수

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 

현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다.”
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.

▣ 입력설명
첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.

▣ 출력설명
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

▣ 입력예제 1
5
172 67
183 65
180 70
170 72
181 60

▣ 출력예제 1
3

출력설명
(183, 65), (180, 70), (170, 72)가 선발됩니다. (181, 60)은 (183, 65) 때문에 탈락하고, (172, 67)은
(180, 70) 때문에 탈락합니다.

 

---

즉 모든 면에서 떨어지는 선수는 탈락이다.

먼저 하나를 기준으로 정렬을 한다. 

위 예제에서 키로 내림차순 정렬을 하면 

 

183 65       --> 이미 키로 모두 이겼기 때문에 뽑힘

181 60       --> 키로 윗사람한테 졌기 때문에 몸무게로 윗사람을 이겨야 하는데 몸무게로도 짐 -> 탈락

180 70       --> 키로 윗사람한테 졌기 때문에 몸무게로 윗사람을 이겨야함 -> 뽑힘

172 67       --> 키로 윗사람한테 졌기 때문에 몸무게로 윗사람을 이겨야함 -> 탈락

170 72      --> 키로 윗사람한테 졌기 때문에 몸무게로 윗사람을 이겨야함 -> 뽑힘

 

 

---

import sys
sys.stdin=open('input.txt','r')

if __name__=="__main__":
    N=int(input())
    players=[list(map(int, input().split())) for _ in range(N)]
    players.sort(reverse=True)
    
    largest=0
    cnt=0
    for x,y in players:
        if y>largest:
            largest=y
            cnt+=1
            
    print(cnt)