백준 1781 컵라면 파이썬 반례 O

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

1781번: 컵라면

처음 이 문제를 봤을때 그냥 우선순위 큐를써서 같은 데드라인 중에서 가장 큰 값을 제외한 나머지를 제거해 결과를 도출하면 되겠다고 생각해 그렇게 구현했다.

import heapq
import sys
input= sys.stdin.readline
n = int(input())
s=[]
for _ in range(n):
    a,b = map(int,input().split())
    heapq.heappush(s,(a,-b))
re=0
while s:
    t = heapq.heappop(s)
    re-=t[1]
    while s and t[0] == s[0][0]:
        heapq.heappop(s)
print(re)

하지만 8%대에서 틀렸습니다가 나왔고 왜 그런가 반례를 찾아보니 데드 라인이 남았는데 삭제해버린 경우.

3
3 9
3 4
1 1

오답:10 정답: 14

데드라인이 긴 경우가 더 많은 라면을 얻을 수 있는 경우.

3
1 25
2 50
2 100

오답: 125 정답: 150

이러한 경우을 고려해 아래와 같이 코드를 만들어 봤다.

import heapq
import sys
input= sys.stdin.readline
n = int(input())
s=[]
for _ in range(n):
    a,b = map(int,input().split())
    heapq.heappush(s,(a,-b))
    
re=0
c=1#현 시간
mins =[]
while s:
    t = heapq.heappop(s)
    re-=t[1]#우선 데드라인 안쪽이니 더해줌
    heapq.heappush(mins,-t[1])#더한 값들을 다 저장해줌
    if s and c ==s[0][0]:#현재 시간과 같은 데드라인을 가지고 있는 문제들을 발견하면 다 빼내야함 
        while s and t[0] == s[0][0]:#계속 빼내는 과정
            w =heapq.heappop(s)#여기서 데드라인이 긴 경우가 더 많은 라면을 얻을 수 있는 경우를 찾아냄
            if -w[1]>mins[0]:#데드라인이 긴 경우가 라면 획득량 > 획득했던 라면량중에 가장 적은 획득량
                re-=heapq.heappop(mins)#가장 적은 획득량을 빼고
                re-=w[1]#지금 라면 획득량을 더해줌
                heapq.heappush(mins,-w[1])#이건 다시 이때까지 획득했던 라면량으로 넣어줌
    c+=1#시간 +1

if re >=2**31:# 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 2**31보다 작거나 같은 자연수인데 넘을 수 있으니 저렇게 해줌.
    print(2**31)
else:
    print(re)