반응형
SMALL
1202 보석 도둑 파이썬
-
백준 1202번 보석 도둑알고리즘 2023. 8. 3. 09:38
N개의 보석의 무게 Mi 와 가격 Vi 가 주어지고, K개의 가방이 담을 수 있는 최대 무게 Ci가 주어졌을 때, 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제입니다. (가방 한 개에는 최대 한 개의 보석만 담을 수 있습니다.) 시도 1. 가장 큰 가격의 보석을 넣을 수 있는 가장 작은 크기의 가방을 선택하여 넣어주도록 했습니다. 우선 가방을 오름차순으로, 보석은 가격순으로 내림차순으로 정렬했습니다. 현재 보석의 무게보다 같거나 큰 가방 중 가장 작은 가방을 선택하도록 했습니다. 이를 위해 이분탐색을 선택해 대입했습니다. def search(num): s,e=0,len(bags)-1 m=(s+e)//2 while snum: e=m-1 else: s=m+1 m=(s+e)//2 while m