https://www.acmicpc.net/problem/1781
시간 2초, 메모리 256MB
input :

• N (1 ≤ N ≤ 200,000)
• 데드라인, 컵라면 수

output :

• 최대 컵라면 수를 출력

조건 :

• 문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다.

---

BOJ 13904 과제 문제와 동일한 문제이다. 고득점 문제에서 부터 계획을 짠다는 생각으로 코드를 작성하는 방식으로 풀었다.

데드라인 에서부터 1일까지 비어있는 공간이 있다면 그 공간을 차지하도록 한다.

import sys

n = int(sys.stdin.readline())
data = []
ans = [0] * 200001

for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    data.append((a, b))

data.sort(key=lambda x:(-x[1]))
for a, b in data:
    while ans[a] != 0:
        a -= 1

    if a == 0:
        continue
    ans[a] = b

print(sum(ans))

테케 추가

테스트케이스가 추가되고 나서 위의 코드는 짤렸다.
시간 복잡도를 매우 소요하는 코드이기 때문에 그렇다.

가장 먼저 생각이 난 방법은 BOJ 10775 공항 문제를 풀 때 사용한 방식이다.
현재 날짜에 대해 이미 큰 값이 존재한다면 새로운 문제를 풀지 않는 것이다.

정렬

이를 위해 컵라면 개수를 내림차순으로 정렬한다. 그러고 나서 날짜를 내림차순한다. 제일 뒤에서 부터 넣어주는 것이 훨씬 편할 것 같아 그렇게 했다.

그래서 정렬 이후에는 union - find를 사용하는데 현재 풀어야 하는 문제의 날짜를 찾아서 parent를 찾는다. 이 값이 0이라면 이미 모든 날짜가 채워진 것이고 그렇지 않은 경우에는 parent - 1의 위치에 union한다.

그러니까 나중에 이전에 찾았던 날짜를 다시 찾은 경우 그 날짜가 아닌 -1에 위치하는 곳으로 옮기고 싶은 것이다.

우선순위 큐

또다른 방식으론 힙을 사용하는 것이다. 예전에 코포 문제 중에 음료를 최대한으로 마시는 문제가 있었는데 그와 유사한 방식을 사용한다.

날짜를 오름차순으로 정렬하여 모든 경우를 비교해서 가장 큰 값만 저장해두는 거다.
현재 정답이라 가지고 있는 리스트의 길이가 현재 보는 원소의 date보다 작은 경우에는 아직 이 날짜에 해당하는 문제를 풀지 않은 것이기 때문에 그냥 push한다.

그런데 그렇지 않은 경우에는 일단 현재의 값을 넣어주고 ans에 위치하는 값 중 가장 작은 값을 빼는 것이다.

# import sys
#
# def find_parent(node):
#     if parent[node] != node:
#         parent[node] = find_parent(parent[node])
#
#     return parent[node]
#
# def union(a, b):
#     parent_a = find_parent(a)
#     parent_b = find_parent(b)
#
#     if parent_a < parent_b:
#         parent[b] = parent_a
#     else:
#         parent[a] = parent_b
#
# n = int(sys.stdin.readline())
# data = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
# ans, parent = [0] * (n + 1), [i for i in range(n + 1)]
#
# data.sort(key=lambda x:(-x[1], -x[0]))
#
# for date, val in data:
#     now_date = find_parent(date)
#
#     if now_date == 0:
#         continue
#
#     union(now_date, now_date - 1)
#     ans[now_date] += val
#
# print(sum(ans))

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
ans, data = [], [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
data.sort(key=lambda x:x[0])

for date, val in data:
    if len(ans) < date:
        heappush(ans, val)
    else:
        heappush(ans, val)
        heappop(ans)
print(sum(ans))