BOJ 1781 : 컵라면 (Python)

문제

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

1781번: 컵라면

 

 

코드

import heapq
import sys
input = sys.stdin.readline
array = []

for _ in range(n):
    deadline, ramen = map(int, input().split())
    array.append((deadline, ramen))

array.sort()

queue = []

for i in array:
    heapq.heappush(queue,i[1]) #힙에 컵라면 수 추가
    if i[0] < len(queue): #데드라인이 queue의 길이보다 작다면
        heapq.heappop(queue)

print(sum(queue))

 

 

풀이

데드라인과 컵라면수를 array라는 배열에 저장하고 array를 오름차순 정렬한다. → 데드라인이 차례대로 커질 것이다.

 

반복문을 통해 queue라는 힙에 컵라면 수를 추가하고 그 데드라인이 queue의 길이보다 작은 경우에, 즉 이미 queue에 있는 문제들을 푸는 것만으로 데드라인을 넘어서는 경우에는 heapq.heappop(queue)를 이용해서 queue에 있는 가장 작은 컵라면 수를 없앤다. 가장 최근에 담은 컵라면수가 가장 작으면 queue에 넣자마자 바로 빠지는 것이다. 그게 아니라면 더 작은 다른 컵라면 수를 없애는 것이고 이는 가장 최근에 담은 컵라면 수가 데드라인 내에 들어올 수 있도록 할 수 있다. 

 

이렇게 풀면 동호가 받을 수 있는 최대 컵라면 수를 구할 수 있다. 

 

 

 

---

 

기타

원래는 데드라인을 기준으로해서 데드라인이 큰 문제부터 차례대로 큐에 집어넣는데 그 중에서도 컵라면 수가 많은 것을 우선적으로 큐에 담을 수 있도록 했다.

데드라인이 현재 큐의 길이보다 길다면, 즉 아직 해당문제를 주어진 데드라인 내에 풀 수 있는 상태라면 큐에 담고, 

데드라인이 현재 큐의 길이보다 짧다면, 즉 해당문제를 주어진 데드라인 내에 풀 수 없는 상태라면 큐에 있는 가장 작은 컵라면수와 해당 컵라면수를 비교해서 해당 컵라면 수가 더 크다면 가장 작은 컵라면 수를 큐에서 없애고 해당 컵라면 수를 넣어서 최대한 많은 컵라면을 가지도록 코드를 짰다.

 

왜인지는 모르겠으나 시간초과가 나왔다. 

 

 

코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())

heap = []

array = []
for i in range(n):
    array.append(list(map(int, input().split())))
    array[i].reverse() #0열이 컵라면수 , 1열이 데드라인
    
array.sort(key=lambda x: (x[0], -x[1]))


for i in range(n):
    if len(heap) < array[i][1]:
        heapq.heappush(heap,[(-1)*array[i][0],array[i][1]])
    elif abs(heap[0][0]) < array[i][0]:
        heapq.heappop(heap)
        heapq.heappush(heap,[(-1)*array[i][0],array[i][1]])

result = 0
while len(heap)!=0:
    result += heapq.heappop(heap)[0]
print(abs(sum(heap)))