[코테] 보석도둑

https://www.acmicpc.net/problem/1202

 

문제설명 : n개의 보석이 각각 무게와 가치가 주어지고, k개의 각각 최대용량이 정해져있는 가방이 있을 때 (가방에는 한개의 보석만 들어갈 수 있습니다.) 가방에 최대한의 가치의 보석을 담으시오.

 

난이도 : 골드 2

 

풀이시간 : 못품...!

 

1차 시도:

import sys
from bisect import bisect_left
input = sys.stdin.readline

n,k = map(int,input().split())
arr = []
for _ in range(n):
    m,v = map(int,input().split())
    arr.append([m,v])
bags=[]
for _ in range(k):
    c = int(input())
    bags.append(c)
arr.sort(key= lambda x : (-x[1],x[0]))
#먼저 가치가 큰거, 가치가 같다면, 무게 가벼운순
bags.sort()
#가방은 작은순
ans = 0
for m,v in arr:
    piv = bisect_left(bags,m)
    #bags에 딱맞는게 있을 수 도 있고 없다면 최대치가 아닌이상 가능한 가장 작은거
    if piv==len(bags):
        #가능한게 없음
        continue
    else:
        ans+=v
        bags= bags[:piv]+bags[piv+1:]

print(ans)

시간제한이 1초(약 2천만)이고, n,k범위가 30만이기 때문에, bisect를 진행하게 되면, $log_2 30만$이 19보다 작은값이므로, 된다고 생각했다가, bags=bags[:piv]+bags[piv+1:] 이 (len(bags)) 즉 O(k)이므로 시간복잡도가 넘어가게 됩니다.(사실 pop은 오래걸리는걸(O(n)) 알고 저걸 쓴건데 저게 됐으면, pop을 안 썼겠지) 

메커니즘은 가치가 크고, 가치가 같다면 무게가 가벼운 순으로 정렬을 합니다. 그리고 가방을 작은순부터 꺼내어 가방의 무게를 기준으로 bisect를 해, 가방의 무게보다는 작되, 가치가 큰 순으로 정답에 더해갑니다.

 

2차 제출:

import sys
import heapq as hp
input = sys.stdin.readline

n,k = map(int,input().split())
jewels=[list(map(int,input().split())) for _ in range(n)]
bags =[int(input()) for _ in range(k)]
jewels.sort(reverse=True)
bags.sort(reverse=True)

q = []
ans = 0
while bags:
    bag = bags.pop()
    #가장 가벼운 가방
    while jewels:
        m,v = jewels.pop()
        #가장 가벼운 보석
        if bag>=m: #가능한 보석은 다넣음
            hp.heappush(q,-v)
        else: #안들어가는건 다시후보에넣기
            jewels.append([m,v])
            break
    if q: #가능한 jewel이 없을수도, 있다면~
        ans-=hp.heappop(q)
        #현재 가능한 보석중 가장 비싼보석 넣기
print(ans)

혼자서는 해결을 못하고 우선순위 큐를 이런식으로 사용한다는 힌트를 보고 다시 짰습니다. 내림차순으로 정렬해서 pop을 했을때 가장 작은것들이 나오게 세팅합니다. 가장 작은 가방 하나를 꺼내고, 그 가방안에 들어가는 보석을 전부 담습니다(들어만 가면 앞으로는 가방의 크기는 같거나 커지기 떄문에 무조건 담을 수 있게 됩니다. 그래서 무게는 신경쓰지않고, 가치를 기준으로 담습니다.). 이때 heap, 우선순위 큐에 담아 항상 최대값을 뽑을 수 있게 합니다.(우선순위큐는 항상 최소값을 반환하므로 -부호를 붙여 담습니다. 꺼낼때 - 붙임주의) 안들어가는건 다음가방에 들어갈 수도있으므로, 다시 넣어주고, 지금까지 넣은것들 중에서 가장 가치가 큰 보석 하나만 답에 추가시켜줍니다. 우선순위큐는 삽입과 삭제 둘다 O(log n) 의 시간복잡도를 갖기 때문에, 총 시간 복잡도는 (n+k)*(log n)이 됩니다.