[코테] 백준 그리디 1781번 문제

1781번 : 컵라면

문제 링크

https://www.acmicpc.net/problem/1781

문제 설명

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호 1 2 3 4 5 6 7 데드라인 1 1 3 3 2 2 6 컵라면 수 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 2의31승보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

문제 풀이

heapq 자료구조를 통해서 정렬된 상태로 저장을 한다. 핵심은 현재 데드라인으로 얻을 수 있는 컵라면이 이전에 저장했던 데드라인의 컵라면들보다 크다면 이전 저장했던 컵라면 중 가장 작은 것을 빼버리고 현재 데드라인으로 얻을 수 있는 컵라면을 더하는 것이다.

from heapq import heappush, heappop

n = int(input())
arr = []

for i in range(n) :
    deadline, cup = map(int, input().split())
    heappush(arr, (deadline, -cup))
    
solve_arr = []

for i in range(n) :
    deadline, cup = heappop(arr)
    
    # 현재 저장한 배열의 길이보다 현재 데드라인이 더 크다면 저장할 수 있는 여유가 있기에 저장
    if len(solve_arr) < deadline : 
        heappush(solve_arr, -cup)
    
    # 1. 현재 데드라인이 저장된 배열의 길이보다 크거나 같고
    # 2. 현재 문제를 풀었을 때 얻을 수 있는 컵라면이 이전 저장한 배열의 컵라면보다 더 많다면 교체 
    elif solve_arr[0] < -cup : 
        heappop(solve_arr)
        heappush(solve_arr, -cup)    

# 문제에서 2의 31승보다 컵라면을 더 가질 수 없기에 아래와 같이 처리
result = sum(solve_arr) 
if result > 2 ** 31 : print(2 ** 31)
else : print(result)