BOJ 1781 - 컵라면

문제

백준 온라인 저지 - 1781번

풀이 과정

마감일을 고려하여 가장 많은 컵라면을 얻을 수 있는 방법을 찾는 그리디 문제입니다.

데드라인의 마지막 날부터 순회를 하면서 해당하는 날 이상의 날짜에 대해서 가장 많은 컵라면을 얻을 수 있는 것을 선택하면 됩니다.

이를 위해 우선 순위 큐 를 두 개 사용해서 하나는 데드라인의 내림차순으로, 다른 하나는 컵라면의 내림차순으로 정렬하여 사용합니다.

코드

import sys
import heapq


N = int(input())
questions = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def init_queue():
    pq = []
    for deadline, cups in questions:
        heapq.heappush(pq, [-deadline, -cups])
    return pq


def solution():
    pq = init_queue()
    day = -pq[0][0]
    answer = 0

    candidates = []
    while day > 0:
        while pq and -pq[0][0] >= day:
            target = heapq.heappop(pq)
            heapq.heappush(candidates, target[1])

        if candidates:
            select = -heapq.heappop(candidates)
            answer += select
        day -= 1

    return answer


print(solution())