문제 소개
해당 문제는 어떤 문제를 풀었을 때 각 문제마다 데드라인이 존재하고 각 문제를 풀 때 1씩 시간이 든다면 최대로 컵라면 수는 몇인가를 묻는 문제이다.
문제 분석
먼저, 최대 컵라면을 만들 수 있는 경우의 수를 계산하기 위해 DFS 혹은 BFS로 문제를 풀 수 있는지 확인해보았다.
DFS나 BFS의 시간 복잡도는 O(노드 수 + 간선 수)이다. 해당 문제에서 최대 문제는 200000개이고 각 간선의 개수는 아래와 같다. 
그럼으로 대충 따져도 100억 이상의 연산을 수행해야한다. 그럼으로 브루트포스 알고리즘은 생략했다.
그럼으로, 아래의 코드와 같이 러프하게 작성하였다.
// 아래의 1번 알고리즘을 기반으로 생성한 코드
import sys, heapq
input = sys.stdin.readline
N = int(input().rstrip())
queue = []
for _ in range(N):
deadline, noodle = map(int, input().split())
heapq.heappush(queue, (-noodle,deadline))
time = 0
totalNoodleCnt = 0
while queue:
n,d = heapq.heappop(queue)
if time < d:
totalNoodleCnt -= n
time += 1
// 아래의 2번 알고리즘을 기반으로 생성한 코드
import sys, heapq
input = sys.stdin.readline
N = int(input().rstrip())
queue = []
for _ in range(N):
deadline, noodle = map(int, input().split())
heapq.heappush(queue, (deadline,-noddle))
time = 0
totalNoodleCnt = 0
while queue:
d,n = heapq.heappop(queue)
if time < d:
totalNoodleCnt -= n
time += 1우선적으로 문제와 각 문제별 컵라면 수를 통해서 우리는 최대 컵라면을 갖기 위해 2가지 알고리즘을 생각해볼 수 있다.
- 문제들 중 컵라면의 수가 가장 많은 문제들 중 데드라인이 이른것 부터
- 문제들 중 데드라인이 이른 것들 중 컵라면 수가 가장 많은 문제부터
즉, 컵라면 수와 데드라인을 통해 데드라인안에 성공할 수 있는 문제들만 추릴려고 했다.
하지만 위의 두 가지 방법은 모두 문제점이 존재한다.
1번과 같이 데드라인보다 컵라면의 수를 먼저 생각해버리면 정작, 컵라면의 큰 문제를 데드라인때문에 생략해버리는 문제가 존재한다.
예를 들어, 아래의 예제와 같이 입력할 경우
3
1 20 // 1번 문제
2 30 // 2번 문제
2 40 // 3번 문제우리는 위의 예제에서 컵라면의 수를 최대로 하는 것부터 찾았기 때문에 3번 문제부터 풀것이다. 하지만 이렇게 풀어버리면 1번 문제를 풀수 있었음에도 불구하고 데드라인이 넘어가 풀지 못하게 된다.
2번과 같이 컵라면의 수보다 데드라인을 먼저 생각해버리면 아래와 같은 예제가 입력될 경우
3
1 20 // 1번 문제
2 30 // 2번 문제
2 40 // 3번 문제최대로 갖기 위해서 2번과 3번 문제를 풀어야하는데, 데드라인을 우선으로 두었기 때문에 1번 문제를 풀어버려 2번과 3번 문제 중 하나의 문제를 풀지 못하는 문제가 발생한다.
해결책
즉, 우리가 풀어야할 문제는 단순히 데드라인이나 컵라면의 수를 갖고 문제를 고를 수 없고, 문제들을 한번씩 살펴 보면서 최선의 경우를 골라내야 한다.
해당 풀이의 초점은 위의 첫 시도의 실패 원인인 데드라인이나 컵라면의 수만으로 간략하게 문제를 판별하는 것이 아니라, 하나씩 문제를 넣어봄으로서 해당 문제가 최선의 경우인지 아닌지를 보는 것이다.
우리가 원하는 것은 컵라면의 최대 값이기 때문에 queue에는 컵라면의 수만 넣는다.
이렇게 조건에 따라 넣지 안넣을지 결정하지 않고 일단 넣는다.
넣은 결과를 통해서 만약, 데드라인이 넘겨질 상황이 발생했을 때 우선순위큐를 사용해서 가장 컵라면의 수가 적은 문제를 제외한다.
적절한 이해를 위해 print문을 중간중간에 찍어서 값이 어떻게 변하는지 살펴보겠다.
import sys, heapq
input = sys.stdin.readline
N = int(input().rstrip())
problems = []
for _ in range(N):
deadline, noodle = map(int, input().split())
problems.append((deadline,noodle))
problems.sort()
print(problems)
queue = []
for d,n in problems:
print(queue)
heapq.heappush(queue,n)
print(queue)
if d < len(queue):
heapq.heappop(queue)
print(queue)
print('----')
print(sum(queue))이렇게 코드를 작성했을 경우, 기본 예제를 돌렸을 때 아래와 같이 출력 결과가 발생한다.
[(1, 6), (1, 7), (2, 4), (2, 5), (3, 1), (3, 2), (6, 1)]
[]
[6]
[6]
----
[6]
[6, 7]
[7]
----
[7]
[4, 7]
[4, 7]
----
[4, 7]
[4, 7, 5]
[5, 7]
----
[5, 7]
[1, 7, 5]
[1, 7, 5]
----
[1, 7, 5]
[1, 2, 5, 7]
[2, 7, 5]
----
[2, 7, 5]
[1, 2, 5, 7]
[1, 2, 5, 7]
----
15위의 출력 결과와 같이 문제들 중 sort함수를 통해 데드라인이 적은 것부터 차례로 정렬했다.
이렇게 정렬된 코드를 통해 먼저 하나씩 문제를 넣어본다.
6개를 주는 문제를 풀었을 경우 문제없이 풀어진다. 문제는 7개를 주는 문제를 풀었을 경우 데드라인이 지나버린다.
6과 7중 가장 낮은 것을 제외시키는 과정을 통해 우리는 해당 문제의 데드라인에 맞는 최대의 문제들을 큐에 넣을수 있다.
이렇게 큐에 넣은 문제들은 최대 컵라면 수를 가져와주는 문제들로 이뤄져 있고 이를 sum을 통해 더하면 최대 컵라면 수가 될 것이다.
최종 제출 코드는 아래와 같다.
최종 코드
import sys, heapq
input = sys.stdin.readline
N = int(input().rstrip())
problems = []
for _ in range(N):
deadline, noodle = map(int, input().split())
problems.append((deadline,noodle))
problems.sort()
queue = []
for d,n in problems:
heapq.heappush(queue,n)
if d < len(queue):
heapq.heappop(queue)
print(sum(queue))