[BOJ] 12018 Yonsei TOTO (Python3)

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 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

문제 풀이

간단한 문제인데 너무 오래걸려서 풀었다.

그냥 순차적으로 계속 마일리지를 받으려고 하니까 알고리즘적으로 단순하고 쉬운게 맞는것 같은데 자꾸 안풀려서 반례를 생각해보려 노력했다. 생각해보니까 무조건 1의 마일리지로 수강신청 성공이 가능한 강의를 먼저 처리해주어야 최대의 수강신청을 성공할 수 있었다.

마일리지의 목록을 내림차순한뒤 l-1이 바로 신청하면 수강신청 성공이 가능한 마일리지가 되므로, p보다 l이 크거나 같다면 l-1에 있는 마일리지를 리스트에 저장해주고, 만약 수강신청인원이 강의 정원보다 적다면 마일리지 1을 리스트에 저장해준다. 그 후, 리스트를 오름차순 정렬하여 순서대로 리스트에 있는 마일리지를 m에서 뺴가면서 0이 될때까지 모두 사용해주면 된다.

코드

n,m = map(int, input().split())

lecture = []
mileages = 0
answer = 0

for i in range(n):
    if m == 0:
        break
        
    p,l = map(int, input().split())

    mileage = list(map(int,input().split()))
    
    mileage.sort(reverse = True)
    mileage = mileage[:l]
    
    if p >= l:
        lecture.append(mileage[l-1])
        
    else:
        lecture.append(1)
        
lecture.sort()
    
for i in lecture:
    if mileages + i > m:
        break
    else:
        mileages += i
        answer+=1
        
print(answer)
    
        
     
       
    

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