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

1202번: 보석 도둑

 

문제!

---

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

---

문제만 읽어 보면 주언진 갯수의 가방으로 최대한 보석을 훔칠때의 최대 가격을 구하기만 하면 되는 문제입니다!

 

여기서 이 부분을 어떻게 효율적으로 풀어낼지가 중요한 문젠데.... 

감이 잡히지 않네요..

 

그래서 일단 바로 

 

시작!

---

가장 먼저

 

 

 

기본적인 변수들을 받아주고

int n, k; // 보석 갯수/ 가방 갯수

long long c[300001];// 가방에 들어갈수 있는 무게

vector<pair<long long, long long>>item;// 보석 무게 / 보석 가격

for (int i = 0; i < n; i++) { // 보석들 받기
		pair<long long, long long>temp;

		cin >> temp.first >> temp.second;
		item.push_back(temp);
		
	}


	for (int i = 0; i < k; i++) { // 가방 무게 받기  // 가방 한개당 한개의 보석
		cin >> c[i];
	}

 

 

 

 

 

이것들을 이제 무게1당 가격의 효율을 따져가며 정렬! 후 가방에 넣어 주려고 했는데(실패....)

bool cmp(pair<long long, long long>&a,pair<long long, long long>& b) {  //효율좋은거 앞으로 + 가벼운거 앞으로
	int memo_a = a.second / a.first;
	int memo_b = b.second / b.first;
	if (memo_a< memo_b) {//무게 1당 가격
		return a < b;
	}
	else if(memo_a == memo_b) {
		return a < b;
	}
	
	return a > b;
}

 

 

정렬을 해버리면 가방의 무게에 맞게끔 넣어주는 부분에서 막히네요.....

 

 

 

 

그래서 생각한 방법이 가방의 무게를 먼저 맞춰주자...

 

양쪽다 sort 해준후

sort(item.begin(), item.end());// 아이템
sort(c, c + k); // 가방

 

 

 

 

 

가방에 들어 갈 수 있는 보석들을 먼저 priority_queue 에 넣어줍시다.

int idx = 0;
priority_queue<int> pq;
for (int i = 0; i < k; i++) {

    while (idx < n && item[idx].first <= c[i]) {
        pq.push(item[idx].second);
        idx += 1;
    }

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

 

 

 

그 후 pq(priority_queue ) 의 상단 값을 불러오면? 끝....

 

 

-----여기서 pq를 왜 초기화 하지 않을까??

        가방 리스트도 현재 정렬되어있기에 다음 가방은 현재가방보다 크므로 

         현재까지의 보석 수 + 다음 나올 보석중 들어갈 수 있는 보석들을 봐야하므로! >> 누적해서 굳이 계속 돌지않게!

 

(이렇게 안하면 가방 하나 처리할 때마다 끝까지 돌아야 될 듯...)

 

 

 

 

 

 

priority_queue ? 

[C++ STL] Priority_queue 사용법

변수가 들어가면 자동으로 정렬해주는 라이브러리 que로 

오름차순으로 정렬됩니다! (그래서 항상 top이 최댓값!) 

 

 

 

 

 

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
#include <queue>

using namespace std;

int n, k; // 보석 갯수/ 가방 갯수

long long c[300001];// 가방에 들어갈수 있는 무게

vector<pair<long long, long long>>item;// 보석 무게 / 보석 가격

priority_queue<int> pq; 

long long answer=0;


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

	cin >> n >> k;
	

	for (int i = 0; i < n; i++) { // 보석들 받기
		pair<long long, long long>temp;

		cin >> temp.first >> temp.second;
		item.push_back(temp);
		
	}


	for (int i = 0; i < k; i++) { // 가방 무게 받기  // 가방 한개당 한개의 보석
		cin >> c[i];
	}
	
	sort(item.begin(), item.end());// 아이템

	sort(c, c + k); // 가방

	int idx = 0;
	for (int i = 0; i < k; i++) {

		while (idx < n && item[idx].first <= c[i]) {
			pq.push(item[idx].second);
			idx += 1;
		}

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


	return 0;

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!