백준 1202번: 보석 도둑

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

1202번: 보석 도둑

문제

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

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

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

입력

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

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

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

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

출력

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

---

기록

 

내가 생각한 풀이법:

1. 보석의 정보를 가치를 기준으로 내림차순 정렬하여 비싼 순서대로 정렬되게 함

2. 가방이 들 수 있는 무게는 오름차순 정렬하여 최대무게가 낮은 순으로 정렬되게 함

3. 가방에 넣을 수 있는 가장 비싼 보석을 찾아 넣음 (1,2에서 정렬을 해놓았기 때문에 반복문만 사용하면 간단하게 됨)

 

n,k=map(int,input().split()) #보석개수 n, 가방개수 k개 입력받기

L_Mi=[] #보석의 무게 리스트
L_Vi=[] #보석의 가치 리스트
for i in range(n):
    Mi,Vi=map(int,input().split())
    L_Mi.append(Mi)
    L_Vi.append(Vi)

jewel=list(zip(L_Mi,L_Vi)) 
jewel.sort(key=lambda x:x[1],reverse=True) #보석의 가치를 기준으로 내림차순 정렬

L_Ci=[] #가방이 들 수 있는 무게 리스트
for i in range(k):
    Ci=int(input())
    L_Ci.append(Ci)

L_Ci.sort() #오름차순 정렬
result=0

for i in range(len(L_Ci)): #가방개수만큼 반복
    
    for j in range(len(jewel)): #보석개수만큼 반복
        
        if(L_Ci[i]>=jewel[j][0]): #보석무게보다 가방으로 들 수 있는 무게가 클때
            result+=jewel[j][1] #가격 더함
            jewel.pop(j) #보석 삭제
            break

    
print(result)

결과

 

작동은 되는데...

시간초과때문에 통과를 못했다

리스트에서 pop()을 하게되면 정렬하는데 시간이 많이걸린다는데 그래서인가?

 

궁금해서 답안을 찾아보니 대부분의 사람들이 우선순위큐를 사용해서 푼 것 같다.

다음엔 우선순위큐를 배워서 이 문제를 다시 풀어봐야겠다.