반응형
https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
소스코드
풀이
★ 보석 가격의 합을 최대한으로 하기 위해서는 우선순위 큐의 최대힙, 최소힙을 모두 이용해야 합니다.
★ 입력받은 보석의 정보를 무게를 기준으로 최소힙 형태로 만들어줍니다.
★ 입력받은 가방의 무게는 오름차순 정렬해주는데, 그 이유는 가방의 무게보다 작거나 같은 보석 무게 중 최댓값이 필요하기 때문입니다. 예를 들어
보석 무게 = [1,30] , [2,65], [5,45]
가방의 무게 = 10, 2
오름차순 정렬되지 않은 채로 보석의 무게대로 가방에 넣으면, 10 가방에는 보석의 가치 중 최댓값인 [2,65]가 들어가고, 2가방에는 [1,30]이 들어가게 되면서 보석 가격 합은 95가 됩니다.
하지만 오름차순으로 정렬한 뒤 넣어보면, 2 가방에는 [2,65], 10 가방에는 [5,45]를 넣을 수 있기에 보석 가격의 합이 110이 됩니다 !
★ 위의 방법을 토대로 가방에 넣을 수 있는 보석을 찾을 때는 최소힙을, 넣은 보석들 중 최대 가치를 찾을 때는 최대힙을 사용하여 답을 구해줍니다 :)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1926번: 그림 (Python, BFS) (0) | 2023.09.28 |
|---|---|
| [백준 알고리즘] 2606번: 바이러스 (Python) (0) | 2023.09.22 |
| [백준 알고리즘] 19638번: 센티와 마법의 뿅망치 (Python) (2) | 2023.08.22 |
| [백준 알고리즘] 23757번: 아이들과 선물 상자 (Python) (3) | 2023.08.22 |
| [백준 알고리즘] 1904번: 01타일 (Python) (2) | 2023.08.22 |