백준 1781번 컵라면

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

1781번: 컵라면

 

문제 설명

문제가 N개 주어지며, 각각의 문제마다 데드라인과 받을 수 있는 컵라면 수가 있습니다.

문제를 데드라인 안에 해결하면 컵라면을 받을 수 있습니다.

모든 문제의 데드라인은 N 이하이며, 푸는데는 1만큼의 시간이 필요합니다.

이때 받을 수 있는 컵라면의 최대 수를 구하는 문제입니다.

 

풀이

데드라인을 이미 넘긴 문제는 풀 필요가 없으므로, 풀어야 할 문제를 골라야 합니다.

데드라인 순서대로 문제를 탐색하며 이전 단계에서 풀기로 한 문제 수가 현재 문제의 데드라인보다 크다면 현재 문제를 풀기로 합니다. 만약 풀기로 한 문제 수와 현재 문제의 데드라인이 같다면 풀기로 한 문제들 중 가장 적은 컵라면을 받는 문제와 현재 문제를 비교합니다. 현재 문제의 컵라면 수가 더 많다면 비교한 문제 대신 현재 문제를 풀기로 합니다. 모든 문제들에 대해 이러한 과정을 반복하면 답을 구할 수 있습니다.

 

풀기로 한 문제들의 컵라면 수를 최소 힙에 넣어두면 '풀기로 한 문제들 중 가장 적은 컵라면을 받는 문제'를 빠르게 찾을 수 있습니다. push연산과 pop연산이 최대 N번씩 실행되므로 $O(NlogN)$의 시간복잡도로 풀 수 있습니다.

 

설명이 다소 장황한 것 같은데 코드를 보면 이해할 수 있을 거라고 생각합니다.

 

코드

hw 자료형을 통해 과제를 나타냈습니다.

사족

골드1치고는 쉬운 것 같아요

처음으로 bits/stdc++.h 써봤는데 너무 편해요