[그리디 알고리즘] YONSEI TOTO

[문제]

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.
성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.
그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

---

[입력]

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)
(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

 

---

[출력]

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

---

[입력 예시]

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

---

[출력 예시]

4

---

[내 풀이]

 

#과목수, 마일리지
n, m=map(int, input().split())
#최대로 들을 수 있는 과목 개수
cnt=0
#각 과목 당 사용해야 하는 마일리지
use=list()

for i in range(n):
    #신청한 사람 수, 수강인원
    p, l=map(int, input().split())
    #각 사람의 마일리지
    mile=list(map(int, input().split()))
    mile.sort(reverse=True)

    if p>=l: #신청한 사람이 수강 인원보다 많거나 같을 때
        use.append(mile[l-1])
    elif p<l:  #신청한 사람이 수강 인원보다 작거나 같을 때
        use.append(1)

use.sort()
for i in use:
    m-=i	#마일리지 사용이 가장 적은 순서대로 빼준다.
    
    if m>=0:
        cnt+=1
    else:
        print(cnt)
        break

if m>=0:
    print(cnt)

 

---

[해설]

 

주어진 마일리지로 최대로 들을 수 있는 과목을 선택해야 하기 때문에,마일리지 사용을 최소로 하는 방법을 고려하는 것이 관건이었다.신청한 사람이 수강 인원보다 작으면 1 마일리지를 투자해도 들을 수 있지만 신청한 사람이 수강 인원과 같아지거나 많아졌을 때, 신청한 사람이 투자한 마일리지를 역순으로 정렬하여만약 수강인원이 3명이고 신청인원이 [4, 3, 2, 1] 마일리지를 각각 투자했다면 마일리지가 같을 때 우선순위가 승준이에게 주어지므로 3번째 즉 2 마일리지를 투자하도록 했다.

 

처음엔 단순이 승준이의 마일리지에서 바로 빼주는 방식을 택했는데,이렇게 하면 마일리지 사용을 최소로 할 수 없다.따라서 각 과목에서 사용해야 하는 마일리지를 list에 따로 모아두고 이를 오름차순 정렬하여 최소 마일리지 사용이 가능한 과목부터 신청해 승준이의 마일리지에서 차감하도록 만들었다.

 

이렇게 하다보니 4를 출력해야 하는데 5가 출력되는 오류가 발생했다.이유는 마일리지가 0보다 작아질 때 과목 수를 출력해서였다.따라서 조건문을 하나 더 사용해 마일리지가 0보다 크거나 같을 때만 과목 수를 추가하도록 했다.

(그런데 다른 사람의 풀이를 보니 출력할 때 단순히 cnt 에 -1을 해주었다. 😭 조건문을 괜히 추가한 듯 싶다.)