📚 12018 - Yonsei TOTO

Yonsei TOTO

이해

사람 수와 마일리지가 주어진다.
매번 각 사람이 마일리지를 얼마나 넣었는지 주어진다.

✔️ 경우의 수

• 신청한 사람 수 > 과목의 수강인원
  • 수업을 무조건 들어야 한다.
• 아니라면,
  • 사람 수를 기준으로 내림차순한다.
  • 수업에서 과목의 수강인원이 n이라면 n번째에 수업을 들어야 최대로 많이 과목을 들을 수 있다.

경우의 수를 이용하여 구현하면 된다.

소스

import sys  
import heapq  
  
read = sys.stdin.readline  
  
n, m = map(int, read().split())  
heap = []  
  
for i in range(n):  
    p, l = map(int, read().split())  
  
    people = list(map(int, read().split()))  
    people.sort(reverse=True)  
  
    mil = people[-1]  
  
    if l > p:  
        heapq.heappush(heap, 1)  
    else:  
        heapq.heappush(heap, people[l-1])  
  
  
res = 0  
answer = 0  

# heap에 데이터가 저장되어 있고, 주어진 마일리지보다 작거나 같다면  
while heap and m - heap[0] >= 0:  
    find_data = heapq.heappop(heap)  
    m -= find_data  
    answer += 1  
  
print(answer)