[BOJ 1781] 컵라면

풀이

같은 데드라인 문제들 중에서 받을 수 있는 컵라면 개수가 최대인 1문제를 선택해서 푸는 것으로 접근했다. 데드라인 마다 모든 문제들을 탐색하면 O(N²)으로 시간초과를 예상했다. 따라서 우선순위 큐를 이용하자는 생각을 하였고, 맞는 방법이었다.

# 잘못된 코드
import sys
import heapq

input = sys.stdin.readline
N = int(input())
problem = []
for _ in range(N):
    heapq.heappush(problem, list(map(int, input().split())))
explore = []
ramen = 0

for i in range(1, N):
    while problem and problem[0][0] == i:
        heapq.heappush(explore, -heapq.heappop(problem)[1])
    if explore:
        ramen -= heapq.heappop(explore)
        while explore:
            heapq.heappop(explore)

print(ramen)

이렇게 구현했지만 틀렸다. 올바른 로직이 아닌 것을 알 수 있었다. 위처럼 구현하게 되면 문제에 있는 입력 예제는 맞을 수 있으나 다른 예제에서 틀리게된다.(각각 데드라인 하나에 문제 딱 하나만 점검하기 때문에 틀림.) 아래 예제를 통해 설명하겠다.

(Ex)
데드라인 : 3 / 3 / 3 / 4 / 4
컵라면수 : 2 / 5 / 9 / 2 / 4

데드라인이 1과 2인 문제들이 없는 것을 알 수 있다. 이 경우에는 데드라인이 3인 문제를 모두 푸는 것이 컵라면을 최대로 받을 수 있으며, 마지막으로 (4,4) 문제를 풀면 컵라면을 최대로 받을 수 있게된다. 이러한 경우를 꼭 생각해주는 연습을 많이 해야겠다...

1. [(데드라인, 컵라면수)]를 오름차순 정렬한다.

2. 맨 앞의 문제부터 일단 푼다. (우선순위 큐에 풀 문제를 저장한다.)

3. 현재 푼 문제의 데드라인이 / 현재 + 이전에 풀었던 문제들 수보다 작으면 우선순위 큐에서 제일 작은 값을 삭제한다. (Min Heap)

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
problems = [list(map(int, input().split())) for _ in range(N)]
problems.sort()

explore = []

for problem in problems:
    # 일단 문제 풀어본다.
    heapq.heappush(explore, problem[1])

    # 데드라인이 같은 문제를 풀었을 때 컵라면 최대로 받을 수 있는 문제만 풀도록 함.
    if problem[0] < len(explore):
        heapq.heappop(explore)  # Min Heap 으로 오름차순 / 제일 작은 컵라면 문제 제거

print(sum(explore))