(1. 문제 설명)
https://www.acmicpc.net/problem/1202
(2차 솔루션)
범주는 우선 순위 대기열을 사용하여 해결됩니다.
카드로도 해결 가능합니다.
카드로 해결
기본 전략은 다음과 같습니다.
- 훔친 보석의 가격을 최대화해야 하기 때문에,
- 보석 가격 내림차순 정렬 후 하나씩 가져가세요.
- 이 시점에서 보석의 무게는 도둑이 가지고 있는 주머니 중 하나에 들어 있어야 합니다.
- 이 시점에서 두 부분으로 검색하려면 가방의 무게도 오름차순으로 미리 정렬해야 합니다.
따라서 보석을 반복할 때 보석이 선택적으로 사용됩니다.
그러나 여기에는 다음과 같은 문제가 있습니다.
- 이번에 아무 가방에나 보석을 넣으면 그 가방은 다음 퀘스트에서 제외되어야 합니다.
- 그러나 이진 검색 배열에서 특정 요소를 제거하려면 O(KlogK) 시간 복잡도가 필요합니다.
- 외부 for 루프를 고려하면 O(NKlogK)이므로 시간 초과됩니다.
따라서 어레이에서 이진 검색을 수행하지 않고
이진 검색은 std::map에서 수행됩니다.
- 별도의 비교를 지정하지 않으면 키를 기준으로 오름차순으로 정렬됩니다.
- O(logN)에서 노드를 삽입하고 삭제할 수 있습니다.
마지막으로 주의할 점은 같은 무게의 가방이 여러 개 있을 수 있다는 것입니다.
따라서 카드에서 주머니를 제거하면 주머니의 수를 따로 세어야 합니다.
우선순위 큐로 해결
카드 솔루션과 약간 다릅니다.
여기 가방마다 반복 하다.
- 먼저 장신구와 가방은 무게가 큰 순서대로 정렬됩니다.
- 가방을 기반으로 외부 for 문을 만듭니다.
- for 문 내에서 현재 가방에 넣을 수 있는 모든 보석의 가격을 MaxHeap에 푸시합니다.
- 다음 보석을 이 가방에 넣을 수 없는 경우,
- 현재 MaxHeap 상단에 있는 보석의 가격을 합계에 더합니다.
이 방법에서는 카드를 사용하여 솔루션에서 고민했던 문제를 해결할 수 있습니다.
현재 가방에 맞는 장신구를 선택하기 때문입니다.
(3번째 코드 – 카드 사용)
(세 번째 코드 – 우선 순위 대기열 사용)