문제 설명

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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) 때문에 탈락합니다.

---

🚀 정답 ⭕

내 풀이

def solution(players):
    players.sort(reverse=True)  # 키를 기준으로 키가 가장 큰 순서대로 정렬 
    weightest=0
    cnt=0
    for height, weight in players:  # 키는 이미 키 순서대로 정렬 하였으니 
        if weight > weightest:      # 몸무게가 가장 크면 
            weightest = weight      # 몸무게 업데이터 
            cnt += 1                # 수를 세
    return cnt


players = [[172,67], [183, 65], [180, 70], [170, 72], [181, 60]]

print(solution(players))

---

대표적 그리디 유형의 문제로 하나를 기준으로 정렬시키고 생각하면 좋다.

관련 그리디 문제들

요격 시스템

단속카메라

회의실 배정

그리디에 익숙하자.

---

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기