[알고리즘] 백준 12018 파이썬 - Yonsei TOTO

 

12018번: Yonsei TOTO

문제

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

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

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

 

문제풀이

n,m=map(int,input().split())
ans=[]
for _ in range(n):
	#01
    a,b=map(int,input().split())
    tmp=list(map(int,input().split()))
    tmp.sort(reverse=True)
    #02
    if a<b:
        ans.append(1)
    else:
        ans.append(tmp[b-1])
ans.sort()
sum=0
for i in range(len(ans)):
	#03
    sum+=ans[i]
    if sum>m:
        print(i)
        quit()
print(len(ans))

- #01 : 값들을 입력받아 각각 a,b와 tmp에 저장한다. tmp는 내림차순 정렬한다.

- #02 : 만약 수강신청 제한 수보다 신청 수가 적다면 최소값인 1을 ans에 추가한다.

           그렇지 않다면 tmp에서 가장 낮은 점수로 수강신청 가능한 점수를 ans에 추가해준다.

           ans는 오름차순 정렬한다. 

- #03 : sum에 ans값을 순차적으로 더해준다.

           만약 sum값이 가지고 있는 마일리지 점수인 m보다 커진다면 

           가능한 과목 수인 i를 출력하고 코드를 종료한다.

           정상적으로 for문이 종료되었다면 ans길이만큼 즉 모든 과목 수를 출력해준다.