백준 문제풀이 - 1781 번

링크 -> https://www.acmicpc.net/problem/1781

1. 요약 및 풀이방법

각 문제에 대한 데드라인과 보상(컵라면)이 주어졌을 때,
최대 보상을 받을 수 있는 경우를 찾는 문제입니다.

우선 heapq 모듈의 heappush를 사용하여 reward를 queue에 추가합니다.
그리고 queue의 길이가 date보다 큰 경우, 데드라인을 넘긴 문제가 있다는 의미이므로
heappop 으로 가장 보상이 작은 경우를 pop 하여 문제를 풀었습니다.

2109-순회강연 문제와 동일하게 풀이 하였습니다.

2. Code

import sys
import heapq

def main():
    N = int(input())
    date_rewards = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

    date_rewards.sort()

    queue = []
    for date, reward in date_rewards:
        heapq.heappush(queue, reward)
        if len(queue) > date:
            heapq.heappop(queue)
    print(sum(queue))


if __name__ == "__main__":
    main()

3. 학습 내용

요즘 알고리즘 문제를 자주 풀다보니 익숙한 문제를 만나게 되었습니다.
한번 풀고 지나갔으면 잊을 수 있는 유형들에 대해
이렇게 반복해서 풀이하면 언젠가 온전히 내 것이 되지 않을까 생각합니다.

4. 결과