과제

• 컵라면과 동일한 문제이지만, n의 범위가 작아서 좀더 비효율적인 알고리즘으로도 해결이 가능하다.
• 그리디 알고리즘으로 풀리는 문제
• 가능한 가장 점수가 높은 과제들을 푸는게 당연히 유리하다. 그리고 과제를 제출할때는 제출가능한 가장 늦은 날짜에 제출하는 것이 유리하다. 그그 경우에 이후의 과제들을 제출할때 선택지를 가장 넒게 남겨주기 때문이다.
• 그러면 이것을 나이브하게 그대로 구현한다면, 과제들을 점수가 높은 순서대로 정렬하고, 각 과제들에 대해서 마감일 이내의 빈 날짜중 가장 늦은 날짜를 찾는 식으로 구현 가능하다. 이 경우의 시간복잡도는 O(nlogn) + O(n*d) 가 된다. 이 문제의 경우에는 이렇게 풀어도 통과 가능하다
• 좀더 효율적으로 구현하는 방법은, 마지막 날부터 첫날까지 순회하면서, 각 날짜에 제출 가능한 과제들을 우선순위 큐에 유지하는 것이다. 어떤 날에 대해, 그 날이 마감인 과제들을 우선순위큐에 추가하고, 우선순위큐에서 가장 점수가 높은 과제를 뽑아서 그날에 제출하도록 하는 방식으로 돌리면 된다. 이 경우에는 과제들을 제출마감일 순서대로 정렬하는데에 O(nlogn)이 걸리고 (정렬 안하고 딕셔너리를 써서 O(n)으로 줄일수도 있다), 최악의 경우 모든 과제들을 한번씩 우선순위큐에 넣고 빼야 하므로 여기에 또다시 O(nlogn)이 걸린다. 날짜별로 순회하는 것까지 생각하면 총 O(nlogn + d)의 시간복잡도로 해결 가능하다. 동일한 문제지만 n제한이 좀더 큰 컵라면같은 문제에서는 이 방식으로 풀어야만 한다.

"""Solution code for "BOJ 13904. 과제".

- Problem link: https://www.acmicpc.net/problem/13904
- Solution link: http://www.teferi.net/ps/problems/boj/13904

Tags: [Greedy]
"""

import heapq
import sys


def main():
    N = int(sys.stdin.readline())
    homeworks = [
        [int(x) for x in sys.stdin.readline().split()] for _ in range(N)
    ]

    homeworks.sort()
    max_day = homeworks[-1][0]
    submittable_homeworks = []
    answer = 0
    for day in range(max_day, 0, -1):
        while homeworks and homeworks[-1][0] >= day:
            heapq.heappush(submittable_homeworks, -homeworks.pop()[1])
        if submittable_homeworks:
            answer += -heapq.heappop(submittable_homeworks)

    print(answer)


if __name__ == '__main__':
    main()