[baekjoon] 백준 12018번(파이썬): Yonsei TOTO

문제

12018번: Yonsei TOTO

- 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다.

- 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다.

- 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

- 성준이는 연세대학교 재학 중인 학생이다.

- 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다.

- 그래서 성준이는 학교 홈페이지를 뚫어버렸다. 그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다.

- 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다)

- 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

- 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다.

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

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

- 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 구하는 문제이다.

알고리즘

- 과목 수와 마일리지를 입력받는다.

- 과목 수만큼 반복하여 과목의 수강인원을 확인하고 과목의 커트라인을 리스트에 담는다.

- 커트라인을 담는 이유는 마일리지가 똑같을 때 성준이에게 우선순위가 주어지고 성준 이후에 과목을 신청하는 사람은 없기 때문이다.

- 과목의 커트라인을 담은 리스트를 내림차순으로 정렬하여 마일리지를 제일 적게 사용해서 과목을 최대한 많이 듣게 한다.

코드

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())
res = []
cnt = 0

# 과목 수 만큼 반복하여 각 과목의 수강인원을 확인하고 결과 리스트에 담는다.
for i in range(n):
    p, l = map(int, sys.stdin.readline().split())
    mileage = list(map(int, sys.stdin.readline().split()))
    mileage.sort()
    # 각 과목을 신청한 사람 수가 과목의 수강인원보다 크거나 같으면
    # 과목에 커트라인을 리스트에 담는다.
    if p >= l:
        for _ in range(p-l):
            heapq.heappop(mileage)

        res.append(heapq.heappop(mileage))

    # 그게 아니라면 마일리지 1을 넣어도 수강할 수 있게 된다.
    # 따라서 마일리지 1을 리스트에 담는다.
    else:
        res.append(1)
        
# 과목의 커트라인을 담은 리스트를 내림차순으로 정렬하여 
# 마일리지를 제일 적게 사용해서 과목을 최대한 많이 듣게 한다.
res.sort(reverse=True)
for i in range(n):
    m -= res.pop()
    # 마일리지가 0보다 작으면 멈춘다.
    if m < 0:
        break
    cnt += 1

print(cnt)

github

junjange/CodingTest