백준 온라인 저지, 자료구조/1202번: 보석도둑 (파이썬 / 백준 골드문제)

문제

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

 

 

문제 정의

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

 

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 M_i와 가격 V_i를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 C_i이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

 

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

 

다음 N개 줄에는 각 보석의 정보 M_i와 V_i가 주어진다. (0 ≤ M_i, V_i ≤ 1,000,000)

 

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 C_i가 주어진다. (1 ≤ C_i ≤ 100,000,000)

 

모든 숫자는 양의 정수이다.

 

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

 

 

접근 방법

- 접근방법(21.07.27(화))
- 1. 보석을 무게를 기준으로 min_heap 정렬을 한다.
- 2. 가방의 무게를 오름차순으로 정렬한다.
- 3. 가방의 무게를 하나씩 탐색하며 해당 무게이하인 보석은 모두 pop한 뒤, 보석의 가치를 기준으로 하는 max heap 정렬한다.
- 4. 이후 max heap에서 가장 큰 가치를 지닌 보석을 더한다.

 

코드

# https://www.acmicpc.net/problem/1202
# 접근방법(21.07.27(화))
# 1. 보석을 무게를 기준으로 min_heap 정렬을 한다.
# 2. 가방의 무게를 오름차순으로 정렬한다.
# 3. 가방의 무게를 하나씩 탐색하며 해당 무게이하인 보석은 모두 pop한 뒤, 보석의 가치를 기준으로 하는 max heap 정렬한다.
# 4. 이후 max heap에서 가장 큰 가치를 지닌 보석을 더한다.

import sys, heapq
n, k = map(int, sys.stdin.readline().split())
jewelries = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
bags = [int(sys.stdin.readline()) for _ in range(k)]

# 1번 수행
jewelry_weight_min_heap = []
for weight, value in jewelries:
    heapq.heappush(jewelry_weight_min_heap, [weight, value])

# 2번 수행
bags.sort()

# 3번 수행
jewelry_value_max_heap = []
total_value = 0
for weight in bags:
    while jewelry_weight_min_heap and jewelry_weight_min_heap[0][0] <= weight:
 w, v="heapq.heappop(jewelry_weight_min_heap)
" heapq.heappush(jewelry_value_max_heap, [-v, w])
 # 4번 수행
 if jewelry_value_max_heap:
 v, w="heapq.heappop(jewelry_value_max_heap)
" total_value +="jew[1]
#" n, k="3," input().split())
# jews="sorted([[1," input().split())) for _ in range(n)]
# bags="sorted([1," range(k)])
# 2
# 65], [5, 23], [2, 99]], key="lambda" x: x[1])
# 1])

# print(jews)
# #print(bags)
# #jews.remove([1, 65])
# result check="[]
#" bag bags:
# i - 1
# while jews:
# jew jew[0] <="bag" and not check:
# check.append(jew)
# break
# else:
# !="0:
#" break

# print(result)



# 접근 방법2> 시간 초과
# 보석의 가치가 높은 순서대로 정렬하고, 가방이 담을 수 있는 최대무게가 높은 순서대로 정렬한다.
# 이후 보석의 가치가 가장 높은 것을 빼고 이 값과 동일한 값하거나 조금 더 큰 값을 가지는 것을 가방에서 이진탐색을 통해 뺀다(bisect_left -> 해당이 위치하게될 왼쪽 인덱스를 출력한다.).
# 이때 사용한 가방은 다시 사용할 수 없으므로 방문처리를 해준다.

# import sys, heapq
# from bisect import bisect_left
# # n, k = map(int, sys.stdin.readline().split())
# # jewelries = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# # bags = [int(sys.stdin.readline()) for _ in range(k)]
# n, k = 3, 2
# jewelries = [[1, 65], [5, 23], [2, 99]]
# bags = [10, 2]

# bags.sort()
# used = [False] * k

# h = []
# for x in jewelries:
#     heapq.heappush(h, [-x[1], x[0]]) # min-heap이기에 보석의 가치를 음수처리하여 제일 상단에 위치하도록 한다. [[보석1의 가치, 보석1의 무게], ...]


# count = 0
# total_value = 0
# # 종료 조건 : 보석이 모두 빠지거나 더이상 담을 가방이 없을 경우
# while h:
#     if count == len(bags):
#         break

#     value, weight = heapq.heappop(h) # 가치가 가장 높은 보석을 뽑는다.
#     jewelry_index = bisect_left(bags, weight) # 현재 주어진 가방에서 보석의 무게로 몇번째 순서인지 확인한다.
    
#     # 주어진 모든 가방의 무게보다 보석의 무게가 큰 경우 pass
#     if len(bags) == jewelry_index:
#         continue

#     else:
#         # 몇몇 가방의 무게보다 보석의 무게가 작고 해당 가방들을 중 하나라도 사용하지 않았다면 보석의 가치를 더하고 해당 가방을 사용한다.
#         for i in range(jewelry_index, k):
#             if used[i] == False:
#                 used[i] = True
#                 count += 1
#                 total_value += abs(value)
#                 break

# print(total_value)

    
# 접근방법 3
# 보석과 가방 모두 무게가 무거운 것을 중심으로 정렬을 한 뒤, 가방 하나 당 들 수 있는 무게 중 가장 가치가 높은 것을 선택한다.

# import sys, heapq
# n, k = map(int, sys.stdin.readline().split())
# jewelries = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# bags = [int(sys.stdin.readline()) for _ in range(k)]

# jewelries.sort(key = lambda x: x[0])
# bags.sort()
# total_value = 0
# while bags:
#     weight_of_bag = bags.pop()
#     temp = 0
#     while jewelries:
#         if jewelries[-1][0] > weight_of_bag:
#             jewelries.pop()
#             continue
#         elif len(bags) > 0 and jewelries[-1][0] <= bags[-1] and temp="value
#" !="0:
#" break
# weight_of_jewelry, value="jewelries.pop()
#" if < value:
# total_value +="temp
#" print(total_value)