📌 사용 알고리즘 :
priority queue, 작은 집합에서 큰 집합으로 합치는 테크닉
처음엔 N 이 10000 이라서 O(N^2) 은 파이썬으로 애매할꺼같아서 O(Nlog^2(N)) 풀이법만 생각했습니다.
📌 첫번째 풀이
풀고보니 O(N^2) 풀이도 아슬아슬하게 통과됩니다. 이번 포스팅에서는 O(N^2log(N) , O(Nlog^2(N)) , O(NlogN) 풀이방법 3가지를 소개하겠습니다.
먼저 날짜를 오름차순으로 접근해봅시다.
가장 급한 일부터 빨리 처리해봅시다.
3
100 2
50 2
30 1
하지만 이럴 경우에는 위와 같은 반례가 생깁니다. 100+30 이 아니라 100+50 이 정답이기 때문입니다.
즉 오늘 당장 가야하는 강연이 있더라도 돈을 더 벌수있는 강연이 존재하고 , 지금 그 강연을 가지않아도 다른 강연을 가면 돈을 더 벌 수 있는 경우가 존재합니다.
하지만 날짜를 오름차순으로 본다면 나중에 갈 수 있는 강의가 지금 당장 가야하는지 여부는 판단할 수 없습니다.
그렇다면 날짜를 내림차순으로 생각해봅시다.
6
10 2
20 2
30 4
40 2
50 3
60 4
먼저 가장 마지막에 끝나는 날짜인 4일때를 봅시다. 이때는 무조건 60 4 를 골라야 합니다.
지금 이 강연을 가지 않으면 3일째는 이득을 보지 못하니깐요. 또한 강연료도 가장 큽니다.
그렇다면 30 4 입력은 버려지게 됩니다. 만약 이 부분을 고려하지 않고 날짜만 본다면
3일째에는 50 의 수익을 2일째에는 40의 수익을 얻습니다.
하지만 1일째에는 30 4 의 입력을 고려할때 최대값을 구할 수 있습니다.
따라서 날짜를 내림차순으로 접근할때는 현재 날짜에 가지 않는 강연을 버려선 안됩니다.
그렇다면 유지를 어떻게 하면 좋을까요?
바로 이전날짜에 해당강연을 갈 수 있도록 추가해주면 됩니다.
하지만 우리는 해당날짜에 갈 수 있는 강연중에 최대값을 구해야하므로 정렬된 상태이어야 하고
매번 원소의 추가가 발생하므로 효율적으로 정렬하기 위해서는 우선순위 큐가 필요합니다.
시간복잡도는 O(N^2logN) 입니다.
현재 날짜에서 갈 수 있는 강연중 최대값을 선택하고 나머지 강연들은 더 적은 날짜로 미룹니다.
2차원 힙을 사용했을때 i 번째 날짜에 가지 않을 강연을 i-1 번째 날짜에 전부 추가하면서 O(NlogN) 의 시간복잡도가 필요하고 모든 날짜에 대해 탐색할때 O(N) 의 시간복잡도가 필요합니다.
아래 코드는 pypy 로 제출해야지 AC 를 받을 수 있습니다.
📌 첫번째 코드
import sys,math,heapq
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]
N=I()
total = 0 ; end = 0
heap=[ [] for _ in range(10001)]
for i in range(N):
p,d=MI()
heapq.heappush(heap[d] , -p)
end = max(end , d)
for i in range(end , 0 , -1):
if heap[i]:
total += -heapq.heappop(heap[i])
while heap[i]:
heapq.heappush(heap[i-1] , heapq.heappop(heap[i]))
print(total)📌 두번째 풀이
i 번째 날짜에 가지 않을 강연은 i-1 날짜로 옮기면서 해당날짜에 갈 수 있는 강연의 수익의 최대값을 매번 고려할 수 있게 되었습니다.
다만 강연을 옮기는 부분을 좀 더 효율적으로 할 수 없을까요?
바로 작은 집합에서 큰 집합으로 합치는 테크닉을 사용하면 됩니다.
만약에 i 번째 날짜에 가지 않을 강연이 10 개가 있고 i-1 번째 날짜에 강연이 1개가 있다면
i 번째 날짜에 있는 모든 강연을 i-1 번째 날짜로 옮기는 것보다
i-1 번째 날짜에 있는 강연을 i 번째 강연으로 옮기는게 더 효율적이지 않을까요?
또한 강연은 총 N 개가 있고 둘 중 더 작은 집합을 큰 집합으로 옮기는 과정에서
항상 집합의 크기가 2배 커진다는 사실을 확인할 수 있습니다.
따라서 최대 log(N) 번이면 모든 강의가 합쳐지게 됩니다.
결론적으로 시간복잡도는 O(Nlog^2(N)) 이 됩니다.
index 변수를 선언함으로써 index 번째 날짜에 강연이 있고 i-1 번째 강연의 수가 더 적으면 index 날짜에 i-1 번째 강연을 전부 넣어줍니다.
반대로 i-1 번째 강연이 더 많다면 index 날짜에 i-1 번째로 강연을 전부 옮겨준 후에 index=i-1 로 바꾸어 주면 두개의 집합을 동시에 다룰 수 있습니다.
📌 두번째 코드
import sys,math,heapq
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]
N=I()
total = 0 ; end = 0
heap=[ [] for _ in range(10001)]
for i in range(N):
p,d=MI()
heapq.heappush(heap[d] , -p)
end = max(end , d)
index = end
for i in range(end , 0 , -1):
if heap[index]:
total += -heapq.heappop(heap[index])
if len(heap[index]) > len(heap[i-1]):
while heap[i-1]:
heapq.heappush(heap[index] , heapq.heappop(heap[i-1]))
else:
while heap[index]:
heapq.heappush(heap[i-1] , heapq.heappop(heap[index]))
index = i-1
print(total)📌 3 번째 풀이
다른사람의 풀이를 찾아보다가 정말 간단하게 푼 코드가 있어서 소개해보자 합니다.
i 번째 날짜를 다르게 생각해보면
i 번째 날짜까지 가야하는 강연의 최대 개수는 i 개 입니다.
따라서 i 번째 날짜에 갈 수 있는 강연을 힙에 모두 넣은 후에
만약 강연의 개수가 i 번째 날짜의 크기보다 더 커지면 최소값을 계속 삭제해주면됩니다.
따라서 i 번째 날짜까지 갈 수 있는 모든 강연중에 최대값만 남게 됩니다.
왜냐하면 i 번째 날짜에 또다른 강연이 들어왔을때 갈 수 있는 모든 강연보다 비용이 작다면 힙에서 추가되지 않기 때문입니다.
반대로 i 번째 날짜에 또 다른 강연이 들어왔을때 갈 수 있는 모든 강연의 최소값보다 크다면 힙에 추가되므로써 문제에서 원하는 최대값을 저장할 수 있습니다.
따라서 최대 2N 번의 원소의 추가와 삭제가 이루어 지므로 시간복잡도는 O(NlogN) 이 됩니다.
📌 3 번째 코드
import sys,math,heapq
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]
N=I()
L=GI(N)
L.sort(key=lambda x:x[1]) # 날짜순 정렬
heap=[]
for cost,day in L:
heapq.heappush(heap , cost)
if day < len(heap):
heapq.heappop(heap) # 최소값 삭제
print(sum(heap))