백준 1781 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 정렬 및 우선순위 큐를 이용하여 O(NlogN)의 시간에 해결할 수 있다
    • 데드라인 기준으로 오름차순 정렬을 수행한다
    • 각 문제의 컵라면 수를 우선순위 큐에 넣으면서, 데드라이을 초과할 결우 최소원소를 제거한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import heapq

    n = int(input())
    array = []
    q = []

    for i in range(n):
        a, b = map(int, input().split(' '))
        array.append((a, b))
    array.sort()

    for i in array:
        a = i[0]
        heapq.heappush(q, i[1])
        if a < len(q):
            heapq.heappop(q)