씨름 선수(그리디)
이분탐색(결정알고리즘) & 그리디 알고리즘
문제 ✏️
씨름 선수(그리디)
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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) 때문에 탈락합니다.
코드 💻
import sys
#sys.stdin=open("input.txt", "rt") # read text
n = int(input())
body = []
for i in range(n):
a, b = map(int, input().split())
body.append((a, b))
body.sort(key=lambda x : (x[0], [1]), reverse=True) # 키로 먼저 정렬
largest = 0
cnt = 0
for x, y in body: # 키에서는 이미 지기때문에 몸무게로만 이기면 됨
if y > largest:
largest = y
cnt += 1
print(cnt)
참고
- 인프런 : 파이썬 알고리즘 문제 풀이
Author And Source
이 문제에 관하여(씨름 선수(그리디)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsj3282/씨름-선수그리디저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)