백준 2109 순회강연 파이썬 풀이

난이도 : 골드3

풀이일 : 2403295

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

2109번: 순회강연

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys, heapq

n = int(sys.stdin.readline())
order = []  # 마감일 정렬 들어온 제안
choice = []  # 강연료 정렬 선택한 제안

for _ in range(n):
    p, d = map(int, sys.stdin.readline().split())
    heapq.heappush(order, [d, p])  # 마감일 기준 정렬로 힙큐 추가

while order:  # 모든 제안에 대해 마감일 오름차순 진행
    d, p = heapq.heappop(order)
    # 마감일 안에 강연이 가득차 있지 않다면 해당 제안 선택
    if d > len(choice):
        heapq.heappush(choice, p)
    else:
        # 마감일 안에 강연이 가득차있다면 강연료 비교 후 선택 결정
        if p > choice[0]:
            heapq.heappop(choice)
            heapq.heappush(choice, p)

# 선택한 제안의 강연료 합 출력
print(sum(choice))

• order : 대학에서 들어온 제안을 heapq를 사용해 마감일을 기준으로 오름차순으로 정렬한다.
• choice : 제안을 승낙하기로 하기로 선택한 강연들을 heapq를 사용해 강연료 기준으로 오름차순으로 정렬한다.
• for 반복문 입력처리에서 order에 마감일 기준으로 제안들을 heapq 추가한다.
• while 반복문은 모든 제안을 확인하는 동안 계속된다.
• 하루에 한 개의 강연을 할 수 있으므로, 마감일이 현재 선택한 제안의 수보다 크다면, 해당 제안을 선택하고 choice 배열에 추가한다. 이때, heapq를 사용하여 강연료가 적은 것에서 많은 것 순서로 정렬될 수 있도록 한다.
• 만약, 마감일이 현재 선택한 제안의 수와 같다면, 선택된 제안 중 강연료가 가장 작은 것과 현재 제안의 강연료를 비교한다. 비교 결과, 현재 강연을 진행하는 것이 이득이라면, 기존의 선택 중 가장 강연료가 작은 것을 제외하고 현재의 강연을 추가한다.
• 반복문에 끝나고 choice 배열안에 있는 선택된 강연들의 강연료 합을 출력한다.

---

느낀점

• 얼마 전에 풀었던 과제 문제와 아주 유사한 문제여서 쉽게 풀 수 있었다. 다른 골드3 문제들에 비해 쉬운 것 같기도 해서 다른 문제들 이론을 조금 더 공부해봐야겠다. 알고리즘을 공부하면서 푸는 게 아니니까 되게 편차가 심한 것 같이 느껴져서 조금 걱정이 되기도 하고.