백준 1202 보석 도둑

문제 URL : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제 접근법 : 결론만 얘기하자면 PQ를 사용하는 문제입니다.  처음 접근을 q로 사용해서 접근했었는데 안되더라구여

문제 에 나와있는 테스트케이스의 힌트

첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

라는 문구가 힌트는 개뿔 오히려 답을 못찾게 생각할수 밖에 없더라구여

제가 좀더 힌트를 주자면 

첫번째 보석을 2번째 가방에도 넣을수있고 2번째 보석을 첫번째 가방에 넣어서 생각할수도 있다

이렇게 생각하면 바로 pq를 사용해서 풀리더라구요

 

소스코드:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

//By 콩순이냉장고 #include<iostream> #include<string> #include<algorithm> #include <vector> #include <queue> using namespace std; int n, k; typedef long long ll; typedef pair<ll, ll> pp; vector<pp> v; vector<int> bag; int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> k;     bag.resize(k);     priority_queue<ll> pq;     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 >> bag[i];     }     sort(v.begin(), v.end());     sort(bag.begin(), bag.end());//정렬해줌     ll sum = 0;     int idx = 0;     for (int i = 0; i < k; i++)     {         while (idx<n&&bag[i] >= v[idx].first)//가방안에 들어갈수있는것들을 모조리 pq에 넣고              pq.push(v[idx++].second);         if (!pq.empty())//pq안에있는값은 bag안에 들어갈수 있는 값들이란것을 보장해줌         {             sum += pq.top();             pq.pop();         }     }     cout << sum << "\n"; }     Colored by Color Scripter

cs

 

모르는것 혹은 궁금한점 또는 제가 어딘가 틀린부분이 있다면 언제든 댓글을 이용해주시길 바랍니다.