2021. 12. 1. 00:48ㆍ알고리즘/자료구조
문제
연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.
성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.
그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.
입력
첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)
(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)
출력
첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.
예제 입력 1
5 76 5 4 36 25 1 36 36 4 4 30 24 25 20 6 4 36 36 36 36 36 36 2 4 3 7 5 4 27 15 26 8 14
예제 출력 1
4
접근 방법
- 각 과목별로 신청한 사람의 마일리지를 내림차순으로 정렬한 뒤, l번째 점수가 몇 점인지 확인해, l번째 점수 + 1을 우선순위 큐에 저장한다.
- 모든 과목을 우선순위 큐에 저장한 뒤, 마일리지를 최대한 활용해 들을 수 있는 과목이 몇 개인지 센다.
코드
# https://www.acmicpc.net/problem/12018
# 접근 방법
# 각 과목별로 신청한 사람의 마일리지를 내림차순으로 정렬한 뒤, l번째 점수가 몇 점인지 확인해, l번째 점수 + 1을 우선순위 큐에 저장한다.
# 모든 과목을 우선순위 큐에 저장한 뒤, 마일리지를 최대한 활용해 들을 수 있는 과목이 몇 개인지 센다.
import heapq
n, m = map(int, input().split())
subject = [[] for _ in range(n)]
h = []
for _ in range(n):
p, l = map(int, input().split())
mileage = sorted(list(map(int, input().split())), reverse = True)
if l > p:
heapq.heappush(h, 1)
else:
heapq.heappush(h, mileage[l-1])
count = 0
while h and m - h[0] >= 0:
x = heapq.heappop(h)
m -= x
count += 1
print(count)
'알고리즘 > 자료구조' 카테고리의 다른 글
백준 온라인 저지, 자료구조 / 13975번: 파일합치기3 (파이썬 / , 백준 골드문제) (0) | 2021.12.08 |
---|---|
백준 온라인 저지, 자료구조 / 11652번: 카드 (파이썬 / , 백준 실버문제) (0) | 2021.12.08 |
백준 온라인 저지, 자료구조 / 1991번: 트리순회 (파이썬 / , 백준 브론즈문제) (0) | 2021.11.29 |
백준 온라인 저지, 자료구조 / 1351번: 무한수열 (파이썬 / , 백준 골드문제) (0) | 2021.11.29 |
백준 온라인 저지, 자료구조 / 17162번: 가희의수열놀이 (파이썬 / , 백준 골드문제) (0) | 2021.11.27 |