1 minute read

12018번 : Yonsei TOTO

문제 링크

https://www.acmicpc.net/problem/12018

문제 설명

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)

(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

문제 풀이

  1. 각 과목 당 수강 인원보다 신청한 사람이 적을 때는 최소 마일리지인 1만 신청
  2. 나머지 경우는 신청한 사람들을 내림차순으로 정렬했을 떄 L-1번째의 마일리지만큼 신청하면 됨 (같은 마일리지일 때는 성준이 우선순위)
from heapq import heappush, heappop

arr = []
count = 0
result = 0

# 과목 수 N, 마일리지 M을 입력 받는다.
N, M = map(int, input().split())

for i in range(N) :
    
    # N만큼 해당 과목의 신청한 사람 P, 과목의 수강인원 L과 신청현황을 입력 받는다.
    P, L = map(int, input().split())
    subs = sorted(list(map(int, input().split())), reverse=True)
    
    # 수강인원보다 신청한 사람이 적을떄 최소 마일리지인 1만 신청하면됨
    if P < L :
        heappush(arr, 1)
        
    # 나머지 경우는 신청한 사람들을 내림차순으로 정렬했을 때 L-1번째의 마일리지만 신청하면 됨
    else :
        heappush(arr, subs[L-1])

# 각 과목당 수강을 하기 위한 마일리지 배열의 항목을 작은 순으로 pop
# 총 마일리지를 안 넘는 한까지 수강 신청
while arr :
    m = heappop(arr)
    
    if count + m <= M : 
        count += m
        result += 1
    
    else : 
        break
        
print(result)

Comments

You May Also Enjoy