[파이썬] 백준 1781 : 컵라면 (골드2)

[파이썬] 백준 1781 : 컵라면 (골드2)

1781번: 컵라면

---

문제

---

풀이

0. 방향성 생각

• 현재 최선의 선택(점수 많이주는거)이 항상 최적의 결과를 불러오지 않는다.
• 데드라인을 고려하면서 컵라면을 선택해야함
• 순차적으로 골랐을 경우, 저장한 자료구조에서 데드라인을 넘긴 경우를 모두 제거해줘야함 <<<<< 중요
• 역순으로 접근하면 현재 시점 t에서는 데드라인이 지난 문제들은 저장한 자료구조에 없다.

1. 입력

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

info = dd(list)
for _ in range(int(input())):
    dead,score = map(int,input().split())
    info[dead].append(score)
info = sorted(list(info.items()))

• defaultdict로 데드라인 : 얻을 수 있는 점수 리스트로 매핑한다
• info에 데드라인 순으로 정렬

2. 탐색

heap = []
answer,deadline = 0,info[-1][0]
for _ in range(deadline):
    
    if info and deadline <= info[-1][0]:
        _,score = info.pop()
        
        for s in score:
            hq.heappush(heap,-s)
            
    if heap:
        answer += hq.heappop(heap)
    deadline -=1
    
print(-answer)

• deadline이 t초면 최대 t개의 문제를 풀 수 있음
• 시작 시간은 현재 deadline
• info가 비어있지 않고, 현재 시간이 데드라인보다 작은 경우 문제를 풀 수 있다.
• 이 경우 score가 담긴 리스트를 뽑아서 힙에 모조리 넣는다. (최대힙이라서 -붙여야함)
• 한 사이클마다 힙에서 최대점수를 가진 문제를 뽑는다. 이후 현재 시점을 줄인다.

 

 

---

전체코드

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

info = dd(list)
for _ in range(int(input())):
    dead,score = map(int,input().split())
    info[dead].append(score)
info = sorted(list(info.items()))

heap = []
answer,deadline = 0,info[-1][0]
for _ in range(deadline):
    
    if info and deadline <= info[-1][0]:
        _,score = info.pop()
        
        for s in score:
            hq.heappush(heap,-s)
            
    if heap:
        answer += hq.heappop(heap)
    deadline -=1
    
print(-answer)

 

코멘트

.