[백준 12018번] Yonsei TOTO (Python)

> 파이썬, 그리디 알고리즘, 정렬

 

 

 

 

 

📖 문제 : Yonsei TOTO (Python)

 

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

 

 

 

 

 

내 코드

if __name__ == "__main__":
    n, m = map(int, input().split())
    c = []

    for _ in range(n):
        student, full = map(int, input().split())
        s_m = list(map(int, input().split()))
        s_m.sort()
        if student - full < 0:
            c.append(1)
        else:
            c.append(s_m[student - full])

    c.sort()
    count = 0

    for i in range(len(c)):

        if m >= c[i]:
            m -= c[i]
            count += 1

    print(count)

 

 

Point ! ⭐️ 

• 예시를 보면, 성준이는 과목 5개중 마일리지 76을 사용하여 들을 수 있는 최대 과목 수를 구하는 문제이다.

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명 정원인 과목에 현재 5명이 신청한 상황이고, 그 5명의 신청한 마일리지는 (36, 25, 1, 36, 36) 이다.

만약 이 과목을 듣는다고 하면, (36, 25, 1, 36, 36)를 정렬하여 (1, 25, 36, 36, 36) 중에서

성준이는 적어도 2명보다 같거나 큰 마일리지로 이 과목을 신청해야하기 때문에 과목 1에서는 성준이는 '25' 만으로 이 과목을 신청할 수 있다. 조건에 "(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)" 이가 있기 때문에, !

 

이런식으로 모든 과목에서 최소 성준이가 그 과목을 들으려면 줘야하는 마일리지는

2과목 : 20 24 25 30 (4/4 -> 4-4 = 0 번째 인덱스 보단 같거나 커야함) -> 20

3과목 : 36 36 36 36 36 36(6/4 -> 6-4 =  2번째 인덱스 보단 같거나 커야함)  -> 36

4과목 : 3 7 (2/4 정원이 안찾기 때문에 마일리지 1만 줘도 수업을 들을 수 있음) -> 1

5과목 : 8 14 15 26 27 (5/4 -> 5-4 = 1 번째 인덱스 보단 같거나 커야함) ->14

 

 

그렇게 각 과목을 듣기 위해선 줘야하는 최소 마일리지는 [25, 20, 36, 1, 4]가 되고, 각 수업을 최대로 많이 듣기 위해서는
낮은 마일리지를 줘도 들을 수 있는 수업부터 들어야 수업을 들을 수 있는 값이 최댓값이 되므로
[1, 4, 20, 25, 36] 로 정렬하여 제출하는 마일리지의 합이 가지고 있는 마일리지 76 보다 같거나 작을 때 까지 들을 수 있는 수업의 수를 구합니다. [1, 4, 20, 25] 로 합은 50에 36 더하면 76이 넘기 때문에 들을 수 있는 수업의 갯수는 4 !

 

 

 

 

 

 

 

 

 

백준

https://www.acmicpc.net/problem/12018

12018번: Yonsei TOTO