1202. 보석 도둑

smsh0722·2022년 5월 18일
0

Greedy

목록 보기
4/5

문제

  • 시간 제한: 1초
  • 메모리 제한: 256MB

Problem Analysis

논리적으로, 작은 가방부터 가능한 최대 가치를 담으면 효율적이다. 이때, Navie 하게 찾으면 시간이 오래 걸린다. 빠르게 후보 보석들을 찾아내고 선택해야 한다.

Algorithm

작은 가방부터 순차적으로 다음을 반복한다.
1. 현재 가방 무게에서 가능한 보석들을 선택지에 추가한다.
2. 선택지에서 최대 가치를 택한다.
(이때, 선택지를 매번 새로 구하는 건 비효율적이므로, 누적시킨다.)

Data Structure

  • bags: 가방을 오름차순으로 priority_queue에 저장
  • gem[]: 보석을 무게 기준 오름차순으로 저장
  • pq: 선택지를 가치 기준 내림차순으로, priority_queue에 저장

결과

Other

시간 복잡도는 O(NlogN) 이다.

profile
Military service - May 31, 2022 ~ Nov. 30, 2023

0개의 댓글