[파이썬] 백준 2109 : 순회강연 (골드3)

[파이썬] 백준 2109 : 순회강연 (골드3)

2109번: 순회강연

---

문제

---

풀이

0. 방향성 생각

• 역순으로 접근하는 그리디

1. 입력

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

table = dd(list)
for _ in range(int(input())):
    p,d = map(int,input().split())
    table[d].append(-p)

info = sorted(list(table.items()))

• 딕셔너리에 값을 음수로 받아서 힙에서 항상 최대값이 출력되도록 할 것
• 입력을 모두 받은 후 info를 순서대로 정렬한다

2. 출력

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

• 순서대로 탐색을 하게되면, 데드라인이 지나지 않은 리스트에서 heappop을 해주어야 하는데, 이렇게 되면 데드라인이 지난 강연들을 제거할 때 시간이 많이 들 수 있다. (n이 작아서 괜찮을지도?)
• 현재 데드라인보다 기간이 많이 남은 강연들은 힙에 넣는다. (x일에는 데드라인이 x일보다 작은 일들은 할 수 x)
• 힙이 비어있지 않으면 비싼 강연부터 계속 뽑아주기

 

---

전체코드

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

table = dd(list)
for _ in range(int(input())):
    p,d = map(int,input().split())
    table[d].append(-p)

info = sorted(list(table.items()))

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

 

코멘트

1781 컵라면과 같은 문제