백준 1202 보석 도둑 [c++]

01 Jul 2022 in Develop / Solving

c++

중간에 자바로 풀고싶은 마음이 머리끝까지 차올랐지만, c++로 해결했다 후.

문제 분석

• 도둑이 보석점을 턴다.
• N개의 보석이 주어진다.
  • 보석은 무게 M과 가치 V로 이루어져 있다.
• K개의 가방이 주어진다.
  • 도둑은 가방에 한 개의 보석만 넣을 수 있고,
  • 각 가방별로 최대 무게가 정해져 있다.
• 도둑이 가져갈 수 있는 최대 보석의 가치는?

입력조건

보석의 수 N 가방의 수 K
N줄에 걸쳐 {
	보석 무게 M 보석 가치 V
}
K줄에 걸쳐 {
	가방 최대 무게 C
}

풀이과정

• 이 문제의 핵심은 정렬이라고 생각한다.

• 받은 보석 배열과, 가방 배열을 모두 오름차순으로 정렬한다.

• 이 상태에서 제일 가져갈 수 있는 무게가 작은 가방부터, 하나씩 올라가며 각 가방에 넣을 보석을 결정한다.

• while문으로 모든 가방을 채우기 전까지 반복한다.

• while문 바깥에 priority queue를 하나 선언한다.

  • 이 queue에는 내가 가방에 넣을 수 있는 가치들이 들어간다.
  • while문 밖에 이를 정의하는 이유는, pq가 초기화되면 안돼기 때문이다.
  • pq에는 항상 지금까지 가능한 모든 보석의 가치가 들어가 있어야 한다.

• while문 안에 다시 while문을 하나 만들어서,
  현재 가방이 버티는 무게보다 보석이 작은 모든 보석을 queue에 넣는 연산을 실행.

• 위의 안쪽 while문을 빠져나오면, 지금 위치의 가방에 넣을 수 있는 보석의 가치들이 queue에 들어있고, 심지어 내림차순으로 정렬되어 있다.

• 이 큐에서 하나를 pop한 뒤, 다음 반복을 실행한다.

• 예외처리도 잊지 말 것!

전체 코드

#include <iostream>
#include <queue>
#include <algorithm>


using namespace std;

struct gem {
    int size;
    long long value;
};

bool comparegem(gem a, gem b) {
    return a.size < b.size;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // N개의 보석, K개의 가방
    int N, K;
    cin >> N >> K;

    // N 개의 보석 크기 나열
    gem gems[N];
    for(int i = 0; i < N; i++)
        cin >> gems[i].size >> gems[i].value;

    // K 개의 가방 크기 나열.
    int bags[K];
    for(int i = 0; i < K; i++) 
        cin >> bags[i];
    // 입력 끝.

    // 정렬.(all 오름차순)
    sort(gems, gems + N, comparegem);
    sort(bags, bags + K);

    int gemidx = 0;
    int bagidx = 0;

    long long ans = 0;
    priority_queue<long long> pq;
    
    // K번째 가방까지 다 넣을 때 까지 반복.
    while(bagidx < K) {

        // 가능한 모든 가치를 queue에 넣음.
        while(gemidx < N && gems[gemidx].size <= bags[bagidx]){
            pq.push(gems[gemidx].value);
            gemidx++;
        }
        if(!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
        bagidx++;
    }
    
    cout << ans << endl;
}