[PS] 1202) 보석도둑

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

1202번: 보석 도둑

Gold2) 1202.보석도둑

 

• 자료구조, 그리디 알고리즘, 정렬, 우선순위 큐

Heap 자료구조 사용 없이 코드를 구성했다가 시간 초과가 났다.

일반적인 Knapsack 문제와 비슷한 구조이고 특징은 가방이 여러 개인 것과 각 가방에 한 개의 보석을 넣을 수 있다는 점.

 

문제의 핵심은 각 가방의 무게 한계보다 작은 무게의 보석 중 가장 가치가 큰 값을 선택하는 것.

최소값과 최대값에 접근하는 문제이기 때문에 Heap 자료구조를 사용하여 시간 복잡도를 줄였다.

 

해결 방법은 다음과 같다.

1. 주어지는 보석과 가방을 모두 Min heap 자료 구조를 사용하여 저장한다.
2. 가장 작은 가방부터 시작하여 반복한다.
   1. 보석에서 무게가 가장 작은 값과 현재 가방의 무게를 비교한다.
   2. 보석의 무게가 더 작아 가방에 넣을 수 있다면 이 보석을 Max_heap에 저장하고 해당 보석을 삭제한다.
   3. 이후 다음 보석에 대해서 위 과정을 반복한다.
   4. 보석의 무게가 더 커진다면 Max_heap에 값이 존재하는지 확인하고 있다면 이를 가방에 넣는 것이므로 결과에 추가한다.
   5. 이후 가방을 제거하고 다음 가방에서 반복한다.

실제 코드는 밑에와 같다.

    def getdata():
        n, k = map(int,input().split())
        stuff = list()
        for _ in range(n) :
            heapq.heappush(stuff, list(map(int,input().split())))
        knap = list()
        for _ in range(k) :
            heapq.heappush(knap,int(input()))
        return n, k, stuff, knap

heap 구조로 데이터를 받았다.

	# 각 가방의 무게 한계에 맞게 가장 값진 보석을 넣어야 함
    # 1. min heap으로 정렬된 knap에서 하나 꺼냄 -> 무게 한계가 가장 작은 가방(logK)
    # 2. 해당 가방의 무게 한계보다 무게가 작은 보석을 새로운 max heap에 저장(보석 제외 -> logN, 보석 추가 -> logN)
    # 3. 이후 max heap에서 하나를 꺼냄 (logN)
    def sol(stuff, knap):
        result = 0
        Max_heap = list()
        while knap :
            item = heapq.heappop(knap) # 1번
            while stuff and stuff[0][0] <= item :
                tmp = heapq.heappop(stuff)[1] # 2번 보석 삭제
                heapq.heappush(Max_heap,-tmp) # 2번 maxheap에 추가
            if Max_heap :
                result += -heapq.heappop(Max_heap) # 3번
            elif not stuff :
                break
        return result

위의 과정을 나타내는 solution 코드이다.

 

Heap을 사용하여 기존에 짰던 O(NK)의 코드에서 O(NlogN)으로 시간복잡도를 줄이고 AC를 받을 수 있었다.