Algorithm - 씨름선수 선발(그리디)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[씨름선수 선발]

 

현수는 씨름 감독이다. 

현수는 씨름 선수를 선발하기 위해 공고를 냈으며, N명의 지원자가 지원을 했다.

현수는 각 지원자의 키와 몸무게 정보를 알고 있으며, 현수는 씨름 선수의 선발 원칙을 다음과 같이 정했다.

 

"다른 모든 지원자와 일대일 비교를 하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다."

 

만약, A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 선발되지 않는다.

 

 

*입력 설명

첫 번째 줄에 지원자의 수 N(5 ≤ N ≤ 50)이 주어진다.

두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어진다. (단, 각 선수의 키와 몸무게는 모두 다름)

 

*출력 설명

첫 번째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하시오.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_27.txt', 'rt')

n = int(input())
body = []
for i in range(n):
    a, b = map(int, input().split())
    body.append((a, b))
body.sort(reverse=True)
largest = 0
cnt = 0
for x, y in body:
    if y > largest:
        largest = y
        cnt += 1
print(cnt)

# 출력 : 3

 

input_27.txt(입력)

5
172 67
183 65
180 70
170 72 
181 60

 

 

중요내용

1. sort() 함수의 인자로 reverse = True를 넣으면, 특정 리스트의 데이터를 내림차순으로 정렬 시킨다.
2. 이중 for문을 사용하지 않고, 입력 받은 데이터를 내림차순으로 정렬 시킨후에 몸무게의 최대 값을 사용하여 지원자들의 몸무게 정보를 비교하는 것이 핵심이다.
3. 위의 원리대로라면, 첫 번째 지원자는 반드시 뽑히는데 이는 키를 기준으로 내림차순 정렬했기 때문에 모든 지원자들 보다 키가 크기 때문에 몸무게를 고려하지 않더라도 반드시 선발된다.