문제 링크입니다: https://www.acmicpc.net/problem/1202
그리디(Greedy) 알고리즘에 우선순위 큐(Priority Queue) 자료구조를 사용해야 했던 문제였습니다.
우선순위 큐 자료구조를 사용하는 부분은 종신1재정2시경3님(http://js1jj2sk3.tistory.com/14)의 코드를 참고했습니다.
알고리즘은 아래와 같습니다.
1. pair<int, int>형 배열에 보석의 정보를 입력받고 int형 배열에 가방의 정보를 입력받습니다.
2. 보석은 무게를 기준으로 오름차순 정렬을 하고 가방은 최대 무게 허용량을 기준으로 오름차순 정렬을 합니다.
3. 핵심은 한 번 확인한 보석은 다시 확인하지 않는 것입니다.
i) 가방의 개수만큼 반복문을 돌립니다.
ii) 해당 가방이 허용할 수 있는 보석까지 우선순위 큐에 넣습니다.
iii) 우선순위 큐는 maxHeap이기 때문에 넣은 보석들 중 제일 비싼 보석이 root에 있습니다.
iv) 따라서, 우선순위 큐의 root에 있는 보석을 가방에 넣어주고 해당 보석을 우선순위 큐에서 pop합니다.
4. 3번을 모든 가방에 대해 반복합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 300000;
int N, K;
int bag[MAX];
pair<int, int> jewelry[MAX];
priority_queue<int> pq; //maxHeap 사용
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0); //cin 실행속도 향상
cin >> N >> K;
for (int i = 0; i < N; i++)
cin >> jewelry[i].first >> jewelry[i].second;
for (int i = 0; i < K; i++)
cin >> bag[i];
//보석(무게 기준)과 가방 오름차순 정렬
sort(jewelry, jewelry + N);
sort(bag, bag + K);
long long result = 0;
int idx = 0;
//무게제한이 낮은 가방부터 최대한 비싼 보석을 넣는 방법
for (int i = 0; i < K; i++)
{
//i 번째 가방의 무게제한에 충족하는 보석 다 넣음
while (idx < N && jewelry[idx].first <= bag[i])
pq.push(jewelry[idx++].second);
//pq의 루트에는 현재 기준 제일 비싼 보석이 들어있음
if (!pq.empty())
{
result += pq.top();
pq.pop();
}
}
cout << result << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1969번 DNA (0) | 2018.08.04 |
---|---|
백준 1543번 문서 검색 (0) | 2018.08.03 |
백준 1700번 멀티탭 스케줄링 (6) | 2018.08.02 |
백준 2529번 부등호 (4) | 2018.08.02 |
백준 1138번 한 줄로 서기 (2) | 2018.08.02 |