while (c.empty() == 0)이 부분에선 총 K번을 반복하게 됩니다. 그리고 if 문 안에 있는 while 에선 최악의 경우엔 N번 수행 합니다. 그리고 while 안에서 우선순위 큐로 넣었기에, O(log N)의 시간복잡도를 가지게 됩니다. 그래서 최종 시간 복잡도는 O(K • N • log2 N)번 입니다.
그리고 가방에 무게와 보석의 무게를 오름차순으로 정렬한 것은 좋은 접근 방식이었습니다. 다른 방법으론 "보석의 가치가 크면서 무게가 작은 것"을 우선순위 큐의 우선순위로 둔 후 가방을 오름차순으로 정렬 후 큐에서 하나씩 들고와서 lower_bound로 가방 무게 중 우선순위 큐의 top에 있는 것의 이상인 값을 구한 후, 그 가방에 우선순위 큐 top을 넣고, 그 가방을 후보에서 제외 시키면 됩니다. 가방의 구조체를 multiset으로 하면 삭제, 수정, 삽입이 모두 log N이니 multiset으로 구조체를 지정 하면 이 방법의 시간복잡도는 O(N • log2 K)입니다. 문제의 대한 접근은 좋았지만 구조체를 잘못 선택한 거니, 구조체만 바꾸시면 해결하실 수 있으실 겁니다. 즐거운 코딩 하십쇼.
예시 코드 :
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
struct compareGEM {
bool operator()(const pair<int,int> a, const pair<int,int> b) {
if (a.second != b.second) return a.second < b.second;
return a.first > b.first;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
priority_queue<pair<int,int>, vector<pair<int,int>>, compareGEM> pq;
multiset<int> bags;
int n, k;
cin >> n >> k;
vector<pair<int,int>> gem(n); // 보석: {무게, 가격}
vector<int> bag(k); // 가방 : 무게
for (auto& p : gem) cin >> p.first >> p.second;
for (auto& p : bag) cin >> p;
for (auto& p : gem) pq.push(p);
for (auto& p : bag) bags.insert(p);
long long int sum = 0;
while (!pq.empty() && !bags.empty()) {
pair front = pq.top();
pq.pop();
auto it = bags.lower_bound(front.first); // 보석 무게 이상을 담을 수 있는 가장 작은 가방 찾기
if (it == bags.end()) continue; // 못 찾은 경우
sum += front.second;
bags.erase(it); // 해당 가방 사용
}
cout << sum << '\n';
return 0;
}

twinshj0604 1년 전
어디 부분에서 시간초과가 나는지 모르겠습니다 알려주시면 감사하겠습니다.