6. 씨름 선수(그리디)

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습
니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자
만 뽑기로 했습니다.”
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니
다.
▣ 입력설명
첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두
다릅니다.
▣ 출력설명
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

 

 

문제풀이

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

n = int(input())

body =[]

for i in range(n):
  height, weight = map(int, input().split()) 
  body.append((height, weight))                      #튜플형태로 append하는 경우!!!!!
  body.sort(key=lambda x: -x[0])                     #튜플의 첫번째 원소로 내림차순정렬 


max =0
cnt =0
for h, w in body:
  if w> max:
    max =w 
    cnt +=1

print(cnt)

Hint

1. 키로 내림차순 정렬했을 때

    "나"를 기준으로 나보다 키가 큰 사람이 있는 경우

    몸무게가 그 사람보다 커야 후보로 살아 남을 수 있다.

 

2. 키는 이미 정렬이 되어 있으므로 키는 더 이상 신경쓰지 말고,

    몸무게를 비교하면서 최대값을 찾아간다. max(a,b)일때 최대값이 바뀔 때마다 cnt를 +1증가 시켜서

    최종적인 cnt를 얻는다.