https://www.acmicpc.net/problem/1781
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
import sys
import heapq
if __name__ == '__main__':
N = int(sys.stdin.readline())
exam_info = []
for _ in range(N):
d, c = map(int, sys.stdin.readline().rstrip().split())
exam_info.append((d, c))
exam_info.sort()
q = []
for exam in exam_info:
dead_line, cup_ramen = exam
heapq.heappush(q, cup_ramen)
if dead_line < len(q):
heapq.heappop(q)
print(sum(q))
# 7
# 1 9
# 1 100
# 2 300
# 2 99
# 3 100
# 5 100
# 5 999
#
# wrong : 1499
# correct : 1599
우선순위 큐를 이용해야한다.
이문제는 보석도둑과 유사하지만 약간 꼬여있다.
우선 문제에서 제공하는 반례만으로 생각지 못한 케이스가 있다.
# 7
# 1 9
# 1 100
# 2 300
# 2 99
# 3 100
# 5 100
# 5 999
위와 같은 케이스에서 1,2,3 일차의 최고값을 구하고 5일차의 최고값인 999를 구하면 오답이다.
1,2,3 일차의 최고값을 구한 후, 4일차에 5일차의 100 그리고 5일차에 5일차의 999를 구해서 1599가 나와야한다.
풀이는 다음과 같다.
1. 입력받은 데이터(데드라인, 컵라면수) 리스트를 데드라인 순으로 정렬한다.
2. 리스트를 순회하며 우선순위큐에 컵라면을 우선 담는다.
3. 담은 컵라면의 데드라인이 이미 담아놓은 전체 컵라면 수보다 작은지 검사한다.
-> 이미 담아놓은 컵라면이 3개라고 가정했을때 이미 3 만큼의 시간을 썼으므로 데드라인이 3미만인것은 담을 수 없다.
4. 담아놓은 전체 컵라면 중 가장 작은 컵라면을 뺀다.
-> 이때 우선순위 큐를 이용해서 최소 컵라면 수를 빼기 때문에 시간복잡도가 좋고 코드도 간결해진다.
5. 담겨있는 전체 컵라면의 합이 정답이다.
전형적인 우선순위 큐 문제.