[백준] 1202번 보석 도둑 (C++)

https://www.acmicpc.net/problem/1202

 

 

이 문제는 N개의 보석과 K개의 배낭이 주어지며 N개의 보석은 가격과, 무게가 주어지며 K개의 배낭은 최대 무게가 주어진다.

 

이때 배낭에는 하나의 보석만 넣을 수 있고 최대 무게를 초과할 수 없다.

 

이때 배낭에 넣을 수 있는 최대 보석의 가치를 구하는 문제이다.

 

테스트케이스를 보고 보석을 순회하며 보석의 최대 무게와 배낭의 최대 무게의 차이가 크지 않는것을 찾는것이 최적이라고 생각하여

 

다음과 같이 코드를 작성하였다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, K;       // 보석 개수, 가방 무게
priority_queue<pii, vector<pii>> pq;
vector<int> v;
bool visited[300001];

void solve() {
    ll answer = 0;
    sort(v.begin(), v.end());

    while(!pq.empty()) {
        int cost = pq.top().first;
        int weight = pq.top().second;
        pq.pop();

        if(K == 0) break;

        int idx = lower_bound(v.begin(), v.end(), weight) - v.begin();

        if(idx >= v.size()) {      // 발견 X
            continue;
        }
        else {
            if(visited[idx]) {
                for(int i = idx; i < v.size(); i++) {
                    if(!visited[i]) {
                        visited[i] = true;
                        K--;
                        answer += cost;
                        break;
                    }
                }
            }
            else {
                visited[idx] = true;
                K--;
                answer += cost;
            }
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> K;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        pq.push({b, a});
    }

    for(int i = 0; i < K; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

하지만 시간초과를 받았고 다른 풀이를 생각해 냈어야 했다.

 

첫번째로 배낭 무게와 배낭을 정렬하여 배낭을 순회하며 배낭에 들어갈 최대 가치의 보석을 찾아야겠다고 생각이 들었다.

 

따라서 최대힙을 사용하여 보석 가치가 배낭 최대 무게보다 커질때까지 보석을 순회하였고 커질 경우 최대힙에서 하나씩 더해준다. -> 배낭에는 최대 하나의 보석만 넣을 수 있기 때문

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, K;
vector<pii> v;
priority_queue<int> pq;
int arr[300001];

bool compare(pii a, pii b) {
    if(a.first == b.first) {
        return a.second > b.second;
    }

    return a.first < b.first;
}

void Print() {
    for(auto it : v) {
        cout << it.first << " " << it.second << endl;
    }

    for(int i = 0; i < K; i++) {
        cout << arr[i] << " ";
    }
}

void solve() {
    sort(v.begin(), v.end(), compare);
    sort(arr, arr+K);

    int idx = 0;
    ll answer = 0;

    for(int i = 0; i < K; i++) {
        int bagsize = arr[i];

        while(idx < N) {
            int weight = v[idx].first;
            int cost = v[idx].second;

            if(weight <= bagsize) {
                pq.push(cost);
                idx++;
            }
            else break;
        }

        if(!pq.empty()) {
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> K;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    for(int i = 0; i < K; i++) {
        cin >> arr[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}