[이분탐색(결정알고리즘)][그리디 알고리즘] - 씨름 선수(그리디 알고리즘)

문제

n명의 씨름선수 중 A라는 선수보다 키도 크고 몸무게도 더 나가면 A 선수는 선출되지 못한다. 이때 n명의 선수 중 선출될 수 있는 선수는 몇명인지 구하여라

문제 풀이 - 1

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

cnt = 0
player.sort(reverse = True)

end_weight = 0
fp = 0
#키순으로 정렬하면 그 전에 사람보다 키가 작으니 몸무게를 비교해야 된다.
for h,w in player:
    if fp < h:
        cnt +=1
        end_weight = w
        fp = h
    elif fp > h:
        if end_weight < w:
            cnt += 1
            end_weight = w
print(cnt)

• 키를 기준으로 정렬했다. (큰 선수부터 비교하는 식으로 진행했다.)
• 이때 키를 기준으로 정렬했기 때문에 키는 신경쓰지 않고 마지막 선수와 현재 선수의 몸무게를 비교해 현재 선수가 몸무게가 더 나가면 선출될 수 있도록 한다.

문제 풀이 - 2

n = int(input())
player = [tuple(map(int,input().split())) for _ in range(n)]
player.sort(reverse = True)
cnt = 0
weight = 0

for h, w in player:
    if w > weight:
        weight = w
        cnt += 1
print(cnt)

해당 몸무게만 비교하면 되기에 현재 선수의 몸무게가 전 선수 몸무게 보다 크면 선출 !!