[백준/파이썬] 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

3 2
1 65
5 23
2 99
10
2

예제 출력 1

164

---

설명

 

해당 문제는 그리디 문제로 우선순위 큐를 이용해 해결했다.

일단 가방의 무게를 오름차순으로 정렬하고 가방에 담을 수 있는 것을 다 우선순위 큐에 넣고 한 개씩 앞에서 부터 빼서 더하면 된다.

 

근데 해당 문제가 분명 논리가 맞는거 같은데 계속 시간 초과가 떠서 다른 사람의 풀이를 봐도 비슷한데

도제체 뭐가 문제지 고민했었다.

 

문제는 입력받을때 input을 sys.stdin.readline()으로 바꾸니까 해결되었다...ㅎㅎ

 

코드