[알고리즘] 씨름선수(그리디)

(문제) 씨름선수(그리디)

---

현수는 씨름 감독입니다.

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

현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.

현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.

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

만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.

입력설명

첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다.

두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다.

각 선수의 키와 몸무게는 모두 다릅니다.

출력설명

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

테스트케이스

입력예제	출력예제
5 172 67 183 65 180 70 170 72 181 60	3
10 177 107 205 88 179 65 165 104 180 50 166 116 199 119 171 70 176 51 207 101	2

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

---

해결방법

그리디 문제는 대체로 정렬로 문제를 해결할 수 있다고 한다.

이 문제는 키로 정렬해도 풀 수 있고, 몸무게로 정렬해도 풀 수 있다.

필자는 몸무게를 정렬하여 풀도록 하겠다.

몸무게는 내림차 순으로 정렬해야 한다.

이유는 각 지원자 보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 존재한 지원자는 탈락이기 때문이다.

그러면 예를 들어서 설명해 보겠다

172 67
183 65
180 70
170 72
181 60

키와 몸무게를 가진 지원자가 있다.

이 지원자들을 몸무게 내림차 순으로 정렬한다.

170 72
180 70
172 67
183 65
181 60

이렇게 된다.

일단 무조건 맨 위에 있는 지원자는 뽑힐 수 있다.

이유는 몸무게를 내림차 순으로 정렬했기 때문에, 맨 위에 사람은 몸무게로는 1등이다.

그러면 이 1등의 키 보다 큰 지원자를 찾으면 그 지원자는 뽑힐 수 있다.

2번째 사람을 보자 2번째 사람은 당연히 1번째 사람보다 몸무게가 낮을 것이다.
(이유는 내림차 순으로 정렬했기 때문에!)

그러나 키는 1번째 사람 보다 키가 크다!

이러면 2번째 사람도 가능하게 된다!

문제의 의도는 키 몸무게 2개 전부 다른 지원자에 비해 떨어지는 사람 뽑힐 수 없는 것이다.

그런 후, 2번째 사람의 키를 따로 저장하자! 이제 2번째 사람의 키가 가장 큰 것을 아는 것이니 저장하는것이다.

3번째 사람을 보자 2번째 사람보다 당연히 무게는 낮을 것이고!

몸무게는 저장했던 몸무게 보다 작다… 그러니 이 사람은 뽑힐 수 없다.

자! 4번째 사람을 보자 2번째 사람보다 당연히 무게는 낮을 것이고, 2번째 사람의 키보다는 이 4번째 사람이 더 크다!

그러면 이 4번째 사람은 뽑힐 수 있다.

이제 또 4번째 사람의 키를 따로 저장해서 나머지와 비교하면서 뽑힐 수 있는 사람의 수를 구하면 되는 것이다.

---

코드

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

arr.sort(key=lambda x: x[1], reverse=True)
# 키와 몸무게 중 적어도 하나는 크거나 무거운 지원자

count = 1
# 몸무게가 가장 무거운 선수의 키
player = arr[0]

# 이미 정렬되어 있어서
for i in range(n):
    if arr[i][0] > player[0]:
        player = arr[i]
        count = count + 1

print(count)