[백준 2109] 순회강연 (Python)

www.acmicpc.net/problem/2109

2109번: 순회강연

 

문제풀이

N, arr : 입력값

hq : 우선순위 큐

idx : arr 리스트의 인덱스

 

우선순위큐를 이용한 그리디 알고리즘 문제이다. 가능한 가장 큰 시간인 10000일 부터 하나씩 내려오면서 해당 날에 가능한 가장 큰 돈을 더하는 방식으로 해결할 수 있다.

 

1. arr 리스트에서 d를 기준으로 역순으로 정렬하기

 

2. 가능한 가장 큰 시간인 10000일부터 1일까지 하나씩 줄여보면서 해당 날에 가능한 강연을 우선순위 큐(hq)에 넣기

- 가능한 강연 중 가장 큰 돈을 결과(ans)에 더하는 그리디 방식으로 해결

 

코드

import sys
import heapq

if __name__ == '__main__':
    N = int(input())
    arr = []
    for _ in range(N):
        p, d = map(int, sys.stdin.readline().split())
        arr.append((d, p))
    arr.sort(reverse=True)
    hq = []
    idx, ans = 0, 0
    for i in range(10000, 0, -1):
        while idx < N and i <= arr[idx][0]:
            heapq.heappush(hq, -arr[idx][1])
            idx += 1
        if hq:
            ans += -heapq.heappop(hq)
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!