greedy 방식으로 접근하려 했으나, 부분 최적해를 구하는 방식이 특이한 문제이다.
내가 시도했던 접근은 bottom-up 방식이 greedy 였으며, 메모리 제한때문에 테이블 구성에 제약이 생기는 것과 local optimal을 구하는 과정이 매끄럽지 못했다.
그래서 찾아본 방법으로 js1jj2sk3.tistory.com/14를 참고했는데, 방법은 다음과 같다.
- Greedy 방식의 정당성 증명 : 무게 제한 순으로 A1, A2, ...의 가방들은 A1이 담을 수 있는 보석은 A2도 담을 수 있으므로, 배낭의 수용량이 높을수록 더 비싼 보석을 넣는게 최적해이다.
- 구현 방법은 우선순위 큐가 핵심인데, 배낭의 무게와 보석의 가치를 정렬하고 i번째 배낭이 담을 수 있는 보석들의 가치 중에서 최대 가치를 뽑아내도록 한다.
고찰
Greedy 알고리즘은 local optimal을 어떻게 구성하는지가 핵심이기 때문에 정렬과도 연관되어 문제가 나오는걸로 보인다.
정답코드
더보기
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX_SIZE 300000
pair<int, int> jew[MAX_SIZE];
int bp[MAX_SIZE] = { 0, };
int N, K;
int main()
{
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> jew[i].first >> jew[i].second;
}
for (int i = 0; i < K; i++) {
cin >> bp[i];
}
//무게 제한이 낮은 가방이 가장 비싼 보석을 넣도록 정렬
sort(jew, jew + N);
sort(bp, bp + K);
long long result = 0;
int idx = 0;
priority_queue<int> pq;
for (int i = 0; i < K; i++) {
//i번째 배낭의 무게 제한에 걸리지 않는 보석들은 다 넣어본다.
while (idx < N && jew[idx].first <= bp[i])
pq.push(jew[idx++].second);
//넣은 값들 중에서 최대 값을 뽑아낸다.
if (!pq.empty()) {
result += pq.top();
pq.pop();
}
}
cout << result;
return 0;
}
'알고리즘 관련 > BOJ' 카테고리의 다른 글
9935 문자열 폭발 (0) | 2021.01.06 |
---|---|
14503 로봇청소기 (0) | 2021.01.04 |
1918 후위 표기식 (0) | 2020.12.31 |
1916 최소비용 구하기 (0) | 2020.12.31 |
11779 최소비용 구하기 2 (0) | 2020.12.31 |