문제 링크입니다: https://www.acmicpc.net/problem/2109
2109번: 순회강연
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다.
www.acmicpc.net
문제의 핵심은 정확히 d일에 강연을 하는 것이 아니라 d일 안에 강연을 하는 것이었습니다.
알고리즘은 아래와 같습니다.
1. 주어진 p와 d를 d를 기준으로 오름차순으로 정렬합니다.
2. 최소힙을 생성하고 정렬된 순서대로 p를 힙에 넣어줍니다.
2.1 단, 힙의 크기가 넣어준 p의 쌍인 d를 초과할 경우, 힙 내에서 가장 작은 p값인 pq.top()을 제거합니다.
3. 2번 과정을 마친 후, 힙 내의 모든 값들을 더한 값이 최대로 벌 수 있는 금액입니다.
개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 13144번 List of Unique Numbers (0) | 2024.04.08 |
|---|---|
| 백준 14469번 소가 길을 건너간 이유 3 (0) | 2024.04.08 |
| 백준 2170번 선 긋기 (0) | 2024.04.03 |
| 백준 14729번 칠무해 (0) | 2024.04.03 |
| 백준 15926번 현욱은 괄호왕이야!! (1) | 2024.03.31 |