[그리디] 씨름 선수

📌

# problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8

 

 

<input>

 

5

172 67

183 65

180 70

170 72

181 60

 

 

# solve:

input 은 키, 몸무게 순대로 주어지고 다른 선수보다 키나 몸무게 둘 중 하나는 커야 하므로,

키나 몸무게 순대로 정렬한 후, 차례차례 비교해 나가면 된다.

만약 키 순대로 정렬한다면 몸무게를 비교해 나가면 되는데,

만약 다른 선수보다 키와 몸무게가 둘다 작다면 출전하지 못한다.

 

 

✔️ code

 

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

n=int(input())
body=[]
cnt=0

for i in range(n):
    h, w=map(int, input().split())
    body.append((h, w))

#키 순대로 내림차순 정렬
body.sort(reverse=True)
largest=0   #몸무게
for x, y in body:
    if y>largest:
        largest=y
        cnt+=1

print(cnt)

 

 

>>>

 

키가 가장  큰 선수와 몸무게가 가장 많이 나가는 선수는 무조건 출전 자격을 얻게 된다.

이 조건을 만족하는지가 의문이었는데, 정렬을 하는 이유에 대해 잘 생각해보지 않아서 몰랐던 것 같다.

largest가 0으로 초기화 되어 있고 body는 내림차순 정렬이 되어있기 때문에,

첫 반복에서 키가 가장 큰 선수는 무조건 cnt+=1 이 된다.

또한 반복문에서 몸무게로 비교를 해가기 때문에 몸무게가 가장 많이 나가는 선수 또한 무조건 cnt+=1이 된다.

그리디 알고리즘은 정렬과 차례차례 비교가 포인트인 알고리즘이란 것을 기억하자 !