2022.02.16 [백준] (python 파이썬) Yonsei TOTO

 

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

12018번: Yonsei TOTO

 

---

풀이

이 문제는 두개의 힙을 이용하여 해결했다.

1. 합격자와 불합격자를 담을 힙을 만든다.

2. Pass의 길이가 뽑는 인원보다 작으면 heappush해준다

3. Pass가 꽉찾으면 Fail에 heappush해준다. 이 때, (-i, i)로 저장해줌

   (불합격자의 최고값과 합격자의 최저점을 비교하기 위해)

4. 합격자의 최저점이 불합격자의 최고점보다 작으면 두 값을 바꿔줌.

5. 각 수강에 필요한 마일리지를 mileage배열에 담고 오름차순 정렬해줌.

6. 작은 마일리지순으로 총 마일리지에 빼주면서 cnt값을 증가시킴

  이 때 m값이 음수가 되면 반복문을 멈춤.

 

이 문제는 각 그룹의 최고점과 최저점을 비교하면서 필요한 값을 찾는 문제이기 때문에 힙을 사용함

import heapq
 
n,m=map(int, input().split())
 
#과목 별로 수강하기 위한 마일리지를 구하는 함수
def Cal(x,y,arr):
    #만약 뽑는 인원보다 적게 지원했으면 마일리지가
    #1만 있어도 합격하므로 1 리턴
    if x<y:
        return 1
    #합격자의 마일리지와 불합격자의 마일리지를 heap에 저장
    Pass = []
    Fail = []
    for i in arr:
        #합격할 수 있는 인원만큼 Pass에 저장
        if len(Pass)<y:
            heapq.heappush(Pass,(i,i))
        #합격인원 만큼 Pass에 저장 됬다면 나머진 Fail에 저장
        #불합격자의 최대점수를 알기 위해 (-i,i)로 저장해서
        #최대값을 루트노드로 나오게 함.
        else:
            heapq.heappush(Fail,(-i,i))
        #합격자의 최저점과 불합격자의 최고점을 비교해서
        #불합격자의 최고점이 더 크면 값을 바꿔줌
        if Fail and Pass[0][1]<Fail[0][1]:
            temp1=heapq.heappop(Pass)[1]
            temp2=heapq.heappop(Fail)[1]
            heapq.heappush(Pass,(temp2,temp2))
            heapq.heappush(Fail,(-temp1,temp1))
    #합격자의 최저점과 동일하면 우선순위를 가지므로
    #합격자의 최저점을 리턴
    return Pass[0][1]
#수강가능한 과목을 카운팅 하기위한 변수
cnt=0
#수강하기 위해 필요한 마일리지
mileage=[]
for i in range(n):
    now,max=map(int,input().split())
    arr = list(map(int, input().split()))
    need_mileage=Cal(now,max,arr)
    mileage.append(need_mileage)
#합격마일리지를 배열에 저장후 정렬
#적게 필요한 마일리지 순
mileage.sort()
for i in mileage:
    m-=i
    #마일리지가 0보다 작아지면 반복문 정지
    if m<0:
        break
    cnt+=1
print(cnt)