[BOJ 1202] 보석 도둑

문제

 

예제

예제 1에서는 첫 번째 보석을 담았을 때가 최대이고,

예제 2에서는 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 담았을 때가 최대이다.

 

구현 1 - 시간 초과

💡 보석을 가격이 높은 순으로 정렬, 가방은 무게가 작은 순으로 정렬하고 비싼 보석부터 차례대로 가방에 담는다

우선순위 큐를 사용하면 자동으로 정렬이 되므로 보석 정보를 priority_queue에 담아주었다.

보석을 담을 수 있는 가방을 찾기 위해 반복문을 사용하였는데, 이 때 한 가방에 2개의 보석이 담기지 않도록 visited 배열을 추가로 사용해주었다.

#include <bits/stdc++.h>

using namespace std;

int n, k; // 보석과 가방의 개수
priority_queue<pair<int, int>> v; // {보석 가격, 무게}
vector<int> c; // 가방에 담을 수 있는 최대 무게
vector<bool> visited; // 가방에 담았는지
int x, y, z; // 보석 무게, 보석 가격, 가방에 담을 수 있는 최대 무게
pair<int, int> vi;
long long ret;

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

    cin >> n >> k;
    // 보석 정보
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        v.push({y, x}); // 가격, 무게
    }
    // 가방에 담을 수 있는 최대 무게
    for (int i = 0; i < k; ++i) {
        cin >> z;
        c.push_back(z);
        visited.push_back(false);
    }
    sort(c.begin(), c.end());

    while (!v.empty()) {
        vi = v.top();
        v.pop();

        for (int i = 0; i < c.size(); ++i) {
            if (c[i] >= vi.second && !visited[i]) {
                ret += vi.first;
                visited[i] = true;
                break;
            }
        }
    }

    cout << ret << "\n";

    return 0;
}

처음에 틀렸습니다 가 떴고, ret을 long long 형으로 바꾸니 시간 초과가 떴다.

 

N = K = 300,000이고 모든 Vi = 1,000,000일 때 정답의 최댓값은 300,000,000,000이므로 int 범위를 넘기 때문에 long long으로 해주어야 한다.

 

구현 2 - 맞았습니다!!

큰돌의 터전 강의를 참고하여 문제를 다시 풀었다.

💡 무게를 적게 담을 수 있는 가방을 기준으로 다 넣어버린다

 

#include <bits/stdc++.h>

using namespace std;

int n, k; // 보석과 가방의 개수
vector<pair<int, int>> v; // {보석 가격, 무게}
vector<int> c; // 가방에 담을 수 있는 최대 무게
priority_queue<int> pq;
int x, y, z; // 보석 무게, 보석 가격, 가방에 담을 수 있는 최대 무게
long long ret;

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

    cin >> n >> k;
    // 보석 정보
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        v.push_back({x, y});
    }
    // 가방에 담을 수 있는 최대 무게
    for (int i = 0; i < k; ++i) {
        cin >> z;
        c.push_back(z);
    }
    sort(v.begin(), v.end());
    sort(c.begin(), c.end());

    int j = 0;
    for (int i = 0; i < k; ++i) {
        while (j < n && v[j].first <= c[i]) pq.push(v[j++].second);
        if (pq.size()) {
            ret += pq.top();
            pq.pop();
        }
    }

    cout << ret << "\n";

    return 0;
}

 

 

아래가 문제를 푸는 핵심적인 코드이다.

for (int i = 0; i < k; ++i) {
    while (j < n && v[j].first <= c[i]) pq.push(v[j++].second);
    if (pq.size()) {
        ret += pq.top();
        pq.pop();
    }
}

 

가방을 기준으로 for문을 돌면서, pq에 가방에 담을 수 있는 보석의 무게를 저장한다.

 

만약 가방에 담을 수 있는 보석이 존재한다면, ret에 보석 가격을 더한다.

✅ Point: 작은 가방에 담을 수 있는 보석은 더 큰 가방에도 담을 수 있기 때문에, pq에 보석이 남아있는 채로 다음 반복문으로 넘어가도 괜찮다!
만약 담을 수 있는 보석이 없을 경우, if문의 조건을 충족하지 않으므로 해당 경우를 생각하지 않을 수 있다.

 

 

 

결과