1781. 컵라면 (Python)

1781번: 컵라면

 

풀이

 그리디하게 현재 시간에서 풀 수 있는 문제의 리스트 중 가장 많은 컵라면 수를 얻을 수 있는 문제를 풀어 컵라면을 얻도록 하면 된다. 이때 현재 시간은 1에서부터가 아닌 제일 큰 데드라인부터 1씩 줄여가면서 풀 수 있는 문제에 대하여 컵라면 수를 우선순위 큐에 넣고 가장 큰 수를 꺼내어 풀면 된다.

 

 문제의 예제를 보면 가장 큰 데드라인은 6이다. 그렇기 때문에 시간은 6부터 시작한다. 현재 시간 6에서 풀 수 있는 문제는 7번이 있다. 7번을 풀고 얻을 수 있는 컵라면 수를 우선순위 큐에 넣어둔다.

• 컵라면 : [1] 

 이제 컵라면 우선순위 큐에서 가장 큰 숫자를 꺼내어 결과에 더해준다.

• 컵라면 : []
• 총 컵라면 개수 : 1 

 

 시간은 줄어들어 3이 되었다(5와 4에는 풀 수 있는 문제가 없고 컵라면 큐도 비었기 때문에 풀 수 있는 문제가 없다). 이제 시간 3에 풀 수 있는 문제 3번과 4번의 컵라면 수를 큐에 넣는다.

• 컵라면 : [2, 1]

 이제 컵라면 큐에서 가장 큰 숫자를 꺼내어 결과에 더해준다.

• 컵라면 : [1]
• 총 컵라면 개수 : 1 + 2 = 3 

 

 이제 시간 2에 풀 수 있는 문제 5번과 6번의 컵라면 수를 큐에 넣는다.

• 컵라면 : [5, 4, 1]

 컵라면 큐에서 가장 큰 숫자를 꺼내어 결과에 더해준다.

• 컵라면 : [4, 1]
• 총 컵라면 개수 : 3 + 5 = 8

 

이제 시간 1에 풀 수 있는 문제 1번과 2번의 컵라면 수를 큐에 넣는다.

• 컵라면 : [7, 6, 4, 1]

 컵라면 큐에서 가장 큰 숫자를 꺼내어 결과에 더해준다.

• 컵라면 : [6, 4, 1]
• 총 컵라면 개수 : 8 + 7 = 15

 

 이제 시간은 0이 되고 탐색은 종료된다.

 

코드

import heapq
import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())  # 숙제의 개수
    problems = []  # 숙제 정보를 담는 최대힙. 값은 (데드라인, 컵라면 수) 튜플의 형태로 담긴다.
    cups = []  # 현재 시간에서 풀 수 있는 문제의 컵라면 수를 담아두는 최대힙
    time = 0  # 현재 시간

    for _ in range(N):
        deadline, cup = map(int, input().split())
        time = max(time, deadline)  # 현재 시간은 가장 큰 데드라인으로 설정한다.

        # problems에 (-deadline, cup)을 넣어둔다.
        # 최대힙으로 사용하기 위해 -deadline을 넣어줬다.
        heapq.heappush(problems, (-deadline, cup))

    res = 0  # 얻을 수 있는 컵라면의 총 개수
    while time > 0:
        while problems:  # 아직 풀 수 있는 숙제들이 남아있는 경우에만
            nextDeadline, nextCup = heapq.heappop(problems)

            # 만약 다음 숙제의 데드라인이 현재 시간과 일치한다면 해당 문제의 컵라면 수를
            # cups에 넣어준다. 이때 최대힙을 구성하기 위해 -nextCup의 형태로 값을 삽입한다.
            if time == -nextDeadline:
                heapq.heappush(cups, -nextCup)
            else:  # 만약 현재 시간에 풀 수 없는 문제라면 다시 problems에 넣어주고 반복문을 종료한다.
                heapq.heappush(problems, (nextDeadline, nextCup))
                break

        # 현재 시간에 풀 수 있는 문제가 있다면 문제를 풀고 컵라면을 얻는다.
        if cups:
            res += -heapq.heappop(cups)

        time -= 1

    print(res)