문제
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.
출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.
import heapq
import sys
input = sys.stdin.readline
n = int(input())
prob = []
for _ in range(n):
a, b = map(int, input().split())
prob.append((a, b))
prob.sort()
q = []
for i in prob:
heapq.heappush(q, i[1])
if i[0] < len(q):
heapq.heappop(q)
print(sum(q))그리디 알고리즘 문제, 해당 입력 받은 배열을 오름차순 정렬을 한 후,
heapq에 push 한다(최소 힙). 이때, push하는 문제의 데드라인이 heapq의 길이(개수)보다 작으면 heapq에서 가장 작은 값을 pop한다.
처음에 데드라인을 문제 풀이 순서로 풀어서, 9%에서 계속 틀렸었다.
다음 입력을 생각해보자
9
5 5
4 6
4 12
3 8
4 18
2 10
2 5
1 7
1 14만약 내가 생각했던 걸로 푼다면,
컵라면의 개수는 14 + 10 + 8 + 18 + 5 = 55 개였을 것이다.
하지만 데드라인이 4인 문제들을 보자. 데드라인이 3인 문제의 컵라면 개수(8) 보다 더 많은 컵라면을 볼 수 있다(18 & 12). 즉, 데드라인이 3인 문제를 빼고 4인 문제를 두문제 푸는 것이 컵라면을 더 많이 얻을 수 있다.
또한 입력을 받은 후, 데드라인을 기준으로 오름차순 정렬을 해야 한다.
정렬을 하지 않는다면, 데드라인이 적은데, 컵라면 개수가 큰 문제가 pop되는 경우가 있을 것이다.
21.04.10 Review
import sys
import heapq
input = sys.stdin.readline
n = int(input())
arr = []
q = []
for _ in range(n):
deadline, num = map(int, input().split())
arr.append((deadline, num))
arr.sort(key = lambda x : (x[0]))
for deadline, num in arr:
if deadline > len(q):
heapq.heappush(q, num)
else:
num_comp = heapq.heappop(q)
if num_comp >= num:
heapq.heappush(q, num_comp)
else:
heapq.heappush(q, num)
print(sum(q))요번엔 풀었다!
첫번째 풀이와는 달리, 먼저 push한 게 아니라 비교를 한 후 push를 진행했다.
또 먼저 입력받을 때의 배열을 sort 하는 거 잊지 말기!
만약
arr.sort()주석 처리를 한다면
q에 남아있는 값들은 [1, 4, 5, 7] 이렇게 된다
원래는 [1, 2, 5, 7]
