HoonK212 GitHub_Blog

[오늘의 백준] 23번째

21 Apr 2024

“13904번”

백준 알고리즘 스터디

  • 자료구조
  • 그리디 알고리즘
  • 정렬
  • 우선순위 큐

문제 : 웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다. 웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력 : 첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다. 다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력 : 얻을 수 있는 점수의 최댓값을 출력한다.

풀이

import sys; input = sys.stdin.readline; sys.setrecursionlimit(10**6)
import heapq
if __name__ == '__main__':

  n = int(input())
  assignments = [[] for _ in range(1001)]
  max_d = 0

  for _ in range(n):
    d, w = map(int, input().split())
    assignments[d].append(w)
    max_d = max(max_d, d)

  heap = []
  answer = 0

  # 마감일이 늦은 날부터 시작해서 과제를 선택
  for d in range(max_d, 0, -1):
    # 현재 날짜에 해당하는 과제들을 힙에 추가
    for w in assignments[d]:
      heapq.heappush(heap, -w)  # 힙에는 점수의 음수를 저장 (최대 힙 구현)
    # 이 날짜에 할 수 있는 과제 중 가장 점수가 높은 과제를 선택
    if heap:
      answer = answer + -heapq.heappop(heap)  # 가장 점수가 높은 과제 추출 (저장된 음수값을 다시 양수로 변환)

  print(answer)

Related posts