[그리디/백준] 1202번: 보석 도둑

-문제: https://www.acmicpc.net/problem/1202

 

 

-정답풀이: 

import heapq

n,k = map(int,input().split())
jewel,bag = [], []
for _ in range(n):
    jewel.append(list(map(int,input().split())))
    
for _ in range(k):
    bag.append(int(input()))
    
jewel.sort()
bag.sort()

count=0
answer=[]
for i in bag:
    #하나의 가방에 담을 수 있는 보석 후보 모두 저장
    while jewel and i >= jewel[0][0]:
        heapq.heappush(answer,-jewel[0][1])
        heapq.heappop(jewel)
    #보석 후보가 있다면 그 중에서 가장 작은 가격(-최대가격)을 넣는다 
    if answer:
        count+=heapq.heappop(answer)
print(-count)

 

-시간초과 풀이 

for문에 while 넣는 구조는 동일한데(?) 안에 내용이 틀린 것 같다. 

일단 주어진 가방은 다 쓰는게 가장 많이 보석을 담을 수 있으니까 for문으로 전체 가방에 대해 탐색하고

while로 해당 가방에 담길 수 있는 보석을 선별하는 과정을 거친다(보석의 무게가 가방 수용 무게보다 작거나 같은 경우)

거친 보석들 중에서 가치가 가장 큰 것을 추가해 나가면 된다(여기서 -jewel[0][1], -count)가 나왔다 

import heapq

n,k = map(int,input().split())
jewel,bag = [], []
for _ in range(n):
    m,v=map(int,input().split())
    jewel.append([m,v])
    
for _ in range(k):
    bag.append(int(input()))
    
jewel.sort(key=lambda x: x[1])
bag.sort()

heapq.heapify(jewel)
answer=0
for i in range(k):
    while(True):
        m,v=heapq.heappop(jewel)
        if m <= bag[i]:
            answer+=v
            break
        else: 
            heapq.heappush(jewel,[m,v])
print(answer)