[맛있는물회] [파이썬] <백준 알고리즘> 1781번 "컵라면"

문제 조건

---

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호데드라인컵라면 수

1	2	3	4	5	6	7
1	1	3	3	2	2	6
6	7	2	1	4	5	1

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N 이하이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 32비트 정수형 범위 이내이다.

 

Input

---

첫 줄에 숙제의 개수 N (1<=N<=200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

 

Output

---

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

 

생각한 아이디어

---

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

https://qrlagusdn.tistory.com/157

[맛있는물회] [파이썬] <백준 알고리즘> 1202번 "보석 도둑"

위의 보석 도둑과 매우 유사하지만 다른듯한 살짝 꼬으면 풀 수 있는 그리디 문제이다.

 

그리디 문제이면서 우선순위 큐를 사용해야한다.

파이썬으로 heapq를 사용하면서 음수로 value값을 넣으면서 max heap을 사용하였다.

 

일단 제일 중요한 것은 컵라면을 sorting하는 것이다.

deadline 기준으로 오름차순으로 정렬을 수행한다.

 

보석도둑과 조금 다른 점은 보석도둑은 1부터 오름차순으로 heap을 사용했지만, 여기서는 뒤에서부터 들어와야한다.

 

왜냐하면 

7

1 9

1 100

2 300

2 99

3 100

5 100

5 999

이런 예제가 있을 수 있다. 

만약 앞에서 온다면

1(100) , 2(300), 3(100), 5(999) 로 1499로 끝나버린다. 

[하지만 답은 4(999) 5(100)이 더해져서 1599이다.]

왜냐하면 time을 기준으로 자신보다 작은 것들만 heap에 넣기때문이다.

 

 

따라서 뒤에서부터 진행하면서 time보다 큰 컵라면들을 heap에 넣는 방식으로 진행해야한다.

즉, 시간을 k에서부터 1까지 진행하면서 자신보다 큰 데드라인을 heap에 넣고 마지막에 pop을 해주면서 계산을 하면 된다.

 

 

 

소스코드

#1781 컵라면
import sys
import heapq 
from collections import deque
input=sys.stdin.readline

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda k: k[0])
arr=deque(arr)
heap=[]
res=0
for time in range(n,0,-1):
    while arr and arr[-1][0]>=time:
        heapq.heappush(heap,-arr.pop()[1])
    if heap:
        res-=heapq.heappop(heap)
print(res)

 

*파이썬 문법 정리