백준 1202번 보석 도둑

N개의 보석의 무게 Mi 와 가격 Vi 가 주어지고, K개의 가방이 담을 수 있는 최대 무게 Ci가 주어졌을 때, 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제입니다. (가방 한 개에는 최대 한 개의 보석만 담을 수 있습니다.)

 

시도 1.

가장 큰 가격의 보석을 넣을 수 있는 가장 작은 크기의 가방을 선택하여 넣어주도록 했습니다.

우선 가방을 오름차순으로, 보석은 가격순으로 내림차순으로 정렬했습니다.

 

현재 보석의 무게보다 같거나 큰 가방 중 가장 작은 가방을 선택하도록 했습니다.

이를 위해 이분탐색을 선택해 대입했습니다.

def search(num):
    s,e=0,len(bags)-1
    m=(s+e)//2
    while s<e:
        if bags[m]==num:
            return m
        elif bags[m]>num:
            e=m-1
        else:
            s=m+1
        m=(s+e)//2
    
    while m<K and bags[m]<num:
        m+=1
    return m

...

for m,v in gems:
    i = search(m)
    while i<K and visited[i]:
        i+=1
    
    if i==K:
        continue
    
    visited[i]=True
    answer+=v

 

 

하지만 결과는 시간초과였습니다.

이분탐색으로 진행했을 때, 이미 보석이 담겨있는 가방이 나왔을 경우 이를 건너가도록 하는 부분이 필요하기도 했고, 양 끝쪽에 대한 풀이도 제대로 되지 않았던 것 같습니다. 무엇보다 log(N)으로 탐색이 끝나는 것이 아닌 최악의 경우 더 많은 시간 동안 보석을 넣을 가방을 찾는 문제가 생기게 되었습니다.

 

 

시도 2.

이전 풀이와 같은 경우 가격이 높은 보석을 우선적으로 가방에 넣어줘야 되겠다고 생각했기 때문에 가방의 무게 순서에 상관없이 보석이 들어가게 되어 어떤 가방에 들어갔는지 안 들어갔는지를 잘 파악하기 어려워 더 풀이가 복잡해졌던 것 같습니다.

그렇기 때문에, 우선 가방에 보석을 순서대로 채워넣도록 해보았습니다. 그리고 최대 보석 가격 합을 구하기 위해서는 가방에 넣을 수 있는 보석 중 가장 가격이 높은 보석을 넣어줘야 겠다는 생각이 들었습니다.

 

그래서 이번에는 보석과 가방을 모두 오름차순으로 정렬했습니다. 이 후, 최대 무게가 작은 가방부터 차례로 넣을 수 있는 보석들 중 가격이 가장 높은 보석을 넣을 수 있도록 해주면 모든 가방에 차례대로 보석을 넣을 수 있을 것이라고 생각했습니다.

현재 가방에 넣을 수 있는 보석들 중 가격이 가장 큰 보석을 계속해서 pop시키기 위해서는 우선순위 큐 혹은 힙큐가 필요하다고 생각했습니다.

 

이전에 자료에서 heapq가 priorityqueue 보다 빠르게 동작한다는 것을 알고 이번에는 heapq로 문제를 풀이했습니다.

 

가방과 보석들을 오름차순으로 정렬해줍니다. 보석의 경우 무게를 우선적으로 정렬해주고, 무게가 같은 경우 가격 순으로 오름차순으로 정렬되도록 해줍니다.

gems = [list(map(int,input().split())) for _ in range(N)]
bags = [int(input()) for _ in range(K)]
bags.sort()
gems.sort()

 

그 다음, 무게가 낮은 가방부터 넣을 수 있는 보석들을 저장하기 위해 따로 배열을 선언해주었습니다.

현재 가방에 넣을 수 있는 가장 가격이 높은 보석을 pop 시키고 다음 가방으로 넘어갔을 경우, 이전에 넣지 않은 보석들도 현재 가방에 넣을 수 있기 때문에 따로 저장해 줄 수 있도록 해주었습니다.

sortedGems=[]
answer = 0

for bag in bags:
    while gems and gems[0][0]<=bag:
        heapq.heappush(sortedGems,-gems[0][1])
        heapq.heappop(gems)
    if sortedGems:
        answer-=heapq.heappop(sortedGems)

가방의 무게보다 낮은 보석들의 가격을 heapq에 모두 넣어주고 넣은 보석은 pop 시켜줍니다.

현재 가방에서 가장 가격이 높은 보석만 정답에 더해줍니다.

 

 

 

 

그리디 문제와 디피 문제에 어려움을 많이 느껴서 좀 더 많은 풀이를 해봐야겠다는 생각이 들었습니다. 이번 문제와 같은 경우 이분 탐색으로도 충분히 풀 수 있다고 생각했지만, 두 번째 시도와는 차원이 다르게 어렵게 풀이하고 있었다고 생각했습니다. 그리디 문제를 풀 경우 좀 더 쉽게 접근하고 모든 경우의 수를 포함시킬 수 있도록 천천히 생각하고 풀어야겠습니다.

내일 또한 그리디와 디피 문제를 풀어 좀 더 완벽하게 접근 할 수 있는 방법을 찾아봐야 될 것 같습니다.