[BOJ/PYTHON] 13904. 과제

백준 문제 링크: https://www.acmicpc.net/problem/13904

문제 요약

과제 마감일 지켜야 점수 받을 수 있음.

얻을 수 있는 점수 최대값

핵심 아이디어

과제는 원래 발등에 불 떨어질 때 해야 하는 것

과제를 하루에 하나씩 처리한다. 기한 당일에 해당 과제를 한다고 간주하면 되는데, 그래야 앞에 기한 더 짧은 다른 과제를 할 수가 있다. 기한(마감일) 기준으로 정렬 후 for문을 돌아가며 점수를 하나씩 append해주면 된다. 점수 리스트에 들어간 점수의 개수는 처리해야 할 과제의 개수이다. 리스트의 점수의 개수가 마감일보다 크면 기한 안에 모든 것을 처리할 수 없기에 점수가 제일 작은 것을 버려주면 된다. heapq로 풀었는데, heapq에서 pop을 하면 점수가 제일 작은 것을 알아서 버려준다.

pop되지 않고 최종적으로 남은 애들은 순서대로 과제를 끝내면 되기에, 점수를 더해준다.

풀이

# gold3-13904. 과제

import sys, heapq
input = sys.stdin.readline

n = int(input())
day_score_list = [list(map(int, input().split())) for _ in range(n)] # 과제 마감일까지 남은 일수, 과제의 점수

day_score_list.sort() # 기한순 정렬
q = []
for day, score in day_score_list:
    heapq.heappush(q, score)
    if len(q) > day: # 기한보다 처리해야 하는 애가 많은 경우
        heapq.heappop(q) # 점수 제일 작은 애를 빼줌

print(sum(q)) # pop되지 않고 남아있는 애들: 각자 날짜에 순서대로 하면 됨

실행 시간

메모리 33324KB, 시간 48ms (python3)