[백준] 12018번 Yonsei TOTO 파이썬 풀이

12018번: Yonsei TOTO

[문제]

---

[코드]

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
result =[]
for _ in range(n):
    p, l = map(int, input().split())
    l_list = list(map(int,input().split()))
    l_list.sort(reverse=True)

    if p < l :
        result.append(1)
    else:
        result.append(l_list[l-1])

result.sort()
count = 0

for i in result:
    if m-i >= 0:
        m -= i
        count += 1
    else:
        break

print(count)

---

[해설]

 

오늘도 늘 그렇듯 Greedy문제... Greedy문제 7일차 어느정도 패턴이 보이기 시작했다

문제를 읽고 어떻게 코드를 구성해야 될지 바로 생각난 문제이다

 

문제 해설은 간단하다.. 하지만 나처럼 문제를 제대로 안읽고 중요 포인트를 누락하면 약간 혼란을 느낄 수도...

 

먼저 n,m 변수를 통해서 과목수와 가진 마일리지를 받는다

그리고 for 문을 통해서 과목수 2개줄을 다시 입력 받는데.. 첫번 째 줄에는 p=신청인원 수, l = 수강신청 가능 인원 수를 받고 다음 에는 신청한 학생이 제시한 마일리지를 리스트로 받는다

 

우리에게 중요한 것은 가장 값싼 마일리지로 최대로 많은 수업을 신청하는 것이다

(이 친구는 분명 학기 중에 후회할 가능성이 100%이다.. 21학점 풀 전공은 에바야.. 삼가 고인의 명복을 미리 빕니다)

 

여기서 중요한 점은 만약 우리 주인공 친구가 공부를 너무 열심히 하기 때문에 같은 학점을 제시했을 때는 우선권이 주인공님에게 있다는 것이다. 따라서 우리에게 필요한 것은 각 과목별로 소비할 수 있는 최소 마일리지 값이다

 

먼저 마일리지 리스트를 내림 차순으로 정렬해준다. (why?  큰 순서대로 해야 우리가 원하는 순서를 알 수 있기 때문에)

 

최소마일리지를 구하는 방법

 

(1) 신청인원이 신청 가능 인원 보다 같거나 많을 때

만약 신청 인원이 신청 가능 인원보다 같거나 많다면 높은 순서에서 신청 커트라인의 마일리지를 우리가 제출하면 된다.

ex) 신청 인원 6 신청 가능 인원 2 

[60 30 20 10 10 10 ] 우리에게 필요한 것은 30마일리지 

 

 

(2) 신청인원이 신청 가능 인원 보다 적을 때

만약 신청 인원이 신청 가능 인원보다 적다면 땡큐다 그냥 1 마일리지만 제출 하면 된다.

 

    if p < l : #(2)
        result.append(1)
    else: #(1)
        result.append(l_list[l-1])

 

여기서 중요한 것은 이를 result라는 새로운 리스트에 저장하는 것이다

이는 다음에 오는 계산과 연결 된다

 

이렇게 for문을 돌면 result에 필요한 최솟값에 마일리지가 채워진다

그럼 우린 이걸 다시 정렬하여 이번에는 작은 순서대로 우리가 가진 m값에서 빼면 된다. 그리고 동시에 count에 1을 더해주면 우리가 원하는 최대로 신청할 수 있는 과목수를 얻을 수 있을 것이다

 

result.sort()
count = 0

for i in result:
    if m-i >= 0: #m-i가 0보다 작다면 마일리지를 소모할 수 없기 때문에
        m -= i
        count += 1
    else: #0보다 작은 경우 for을 종료한다
        break

print(count)