-
[백준 2109] 순회강연 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 11:24
문제풀이
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)
결과
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!
'Algorithm & Problem Solving > 그리디 알고리즘(Greedy)' 카테고리의 다른 글
[백준 1715] 카드 정렬하기 (Python) (0) 2021.01.28 [백준 1744] 수 묶기 (Python) (0) 2021.01.22 [백준 5002] 도어맨 (Python) (0) 2021.01.22 [백준 1202] 보석 도둑 (Python) (0) 2021.01.22 [백준 17615] 볼 모으기 (Python) (0) 2021.01.19