5-f 질문입니다

우선순위큐 크기가 가방 총 크기보다 클 때만 큐에서 빼는 로직을 작성했는데 왜 틀렸는지 궁금합니다

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
priority_queue<ll> pq;
ll n,k,ret;
int main(){
    cin>>n>>k;
    pair<ll,ll> v[n]; //jewelry
    ll bag[k];

    for (int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    for (int i=0;i<k;i++){
        cin>>bag[i];
    }
    int idx=0; //bag index

    sort(v,v+n);
    sort(bag,bag+k);
   
    int idx2=0;
    while (idx2<n){
        while (idx<k && idx2<n){
            if (bag[idx]<v[idx2].first) idx++;
            else{
                if (pq.size()==k){
                    if (v[idx2].second>pq.top()){
                        pq.pop();
                        pq.push(v[idx2].second);
                    }
                }else if (pq.size()<k) pq.push(v[idx2].second);
            }
            
            idx2++;
        }
    }
    while (pq.size()){
        ret+=pq.top(); pq.pop();
    }
   cout<<ret;

안녕하세요, 인프런 AI 인턴입니다. ililil님.

질문하신 내용에 대해 설명드리겠습니다. 우선순위 큐를 사용할 때 가방의 총 크기를 확인하는 로직으로 접근하셨는데, 이 과정에서의 문제점을 아래에 설명드리겠습니다.

문제점 분석

가방과 보석 매칭:
- bag와 v (보석)의 정렬 순서와 비교 로직을 보면, 현재 idx로 가방의 크기를 확인하고 idx2로 보석의 무게를 탐색합니다.
- bag[idx] < v[idx2].first 이 조건을 통해 가방이 해당 보석을 담을 수 있는지를 확인하지만, 가방의 크기보다 보석의 무게가 큰 경우를 처리하지 않습니다.
우선순위 큐 조건:
- 기존의 코드는 pq의 사이즈가 k보다 작을 때는 v[idx2].second (보석의 가치)를 pq에 추가합니다. 하지만, pq의 사이즈가 이미 k와 같을 때는 v[idx2].second가 pq의 최솟값보다 큰 경우에만 최솟값을 업데이트합니다.
- 이 로직은 어느 정도 올바르게 작동할 수 있으나, 전체 보석을 고려한 최적의 조합을 담기 위해서는 반복문 내부에서 최대한 많은 가치를 큐에 넣고 나중에 필요하지 않은 작은 가치를 빼는 방식으로의 접근이 필수적입니다.

대안 제안

정렬된 보석과 가방을 효율적으로 이용:
- 보석과 가방을 정렬한 후에, 가능한 무게 내에서 가치가 높은 보석을 최대한 가치가 높은 순으로 큐에 넣어야 합니다.
- 가방 안에 담을 수 있는 보석을 큐에 추가하며, 이후 가방에 남은 공간이 있거나 가방이 채울 수 있는 가치보다 가치가 덜한 보석이 있다면 이를 교체하되 큰 가치로 업데이트합니다.
우선순위큐에 대한 추가 논리 적용:
- 큐의 크기가 k를 넘는 경우에 대한 명확한 처리보다는, 각 가방 단위로 최대 가치를 산정하고 이를 계속해서 업데이트하여 최종 가치를 산출하는 방식으로 로직을 보완해야 합니다.

아래 유사한 질문 링크에서 추가 설명을 확인할 수 있으니 보시길 추천드립니다:

5-F 재질문드립니다 :)

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

문제점 분석

대안 제안