백준 1202 C++ "보석 도둑" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 크게 sort 와 우선순위 큐를 활용하여 문제를 해결 했다.

 

필자는 우선순위 큐를 처음에 생각 못하여 binary_Search() 를 진행했지만 실패했다.

 

필자는 다음과 같은 사고 과정으로 문제를 해결했다.

 

가방의 무게는 오름차순으로 정렬한다.

보석 배열은 값어치 순이 아닌 무게 순으로 오름차순으로 정렬한다.

 

while 문을 실행하여 

가방을 기준으로 보석들의 무게가 가방의 담을 수 있는지 점검하고 담을 수 있다고 하면
우선순위 큐에 넣는다.

우선순위 큐에 넣어진 값은 보석의 값어치가 높은순으로 정렬되어 있어

매번 하나의 가방을 검사할 때마다 가장 높은 값어치를 꺼내 sum에 더한다.

 

여기서 필자는 처음 의문이 들었다.

다른 값어치로 이루어진 중복된 무게를 가진 보석들을 우선순위 큐에 넣게 되면
똑같은 가방에 여러개의 보석을 넣는 셈이 아닌가?? 라는 생각을 했지만.

 

현재 가방 배열은 무게가 작은 순서대로 오름차순 되어 있어

1번 가방에 넣지 못하면 자연스럽게 2번가방에 넣을 수 있게 된다.

 

이 사고 과정만 된다면 문제를 쉽게 해결 할 수 있다.

 

아래는 소스코드 해설이다.

작동 방식 설명:

1. 초기화 및 입력 처리 (Input 함수):
   • N개의 보석 정보와 K개의 배낭 정보를 입력받아 각각 jinju와 backpack 벡터에 저장합니다.
   • 보석 리스트는 무게가 가벼운 순으로 정렬됩니다. 같은 무게라면 가치를 기준으로 내림차순 정렬합니다.
   • 배낭 리스트는 오름차순으로 정렬되어, 작은 무게의 배낭부터 순서대로 탐색할 수 있게 합니다.
2. 게임 시작 (GameStart 함수):
   • pq는 현재 선택할 수 있는 보석들 중 가치를 최우선으로 비교하는 구조입니다 (내림차순 정렬, priority_queue 사용).
   • idx는 현재 탐색 중인 보석의 인덱스를 가리킵니다.
   • 각 배낭에 대해 다음 과정을 반복합니다:
     • backpack[i]의 용량이 수용할 수 있는 보석들을 pq에 추가합니다. 이때, 현재 배낭의 무게 제한보다 작거나 같은 보석들만 넣습니다.
     • 만약 pq가 비어 있지 않다면, 가장 가치가 높은 보석을 선택해 sum에 더합니다. 그리고 pq에서 제거합니다.
   • 이 과정은 마치 최적의 경로를 탐색하듯, 현재 선택 가능한 최고의 가치를 선택하며 진행됩니다.
3. 백트래킹의 유사성:
   • 이 과정은 백트래킹 접근법처럼 보석을 선택하며 최적의 해결책을 찾아갑니다. 즉, 각 배낭에 대해 가능한 모든 선택지를 탐색하되, 최적의 가치를 선택하는 방식입니다.
   • 한 번 선택한 보석은 다시 고려하지 않으며, 더 나은 선택지를 위해 탐색 경로를 "백트래킹"하지 않고 효율적으로 처리합니다.

 

[소스 코드]

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


using namespace std;
typedef pair<long, int> Node;

bool cmp(Node a, Node b) {
	if (a.first == b.first) {
		return a.second > b.second;
	}
	return a.first < b.first;
}
bool backpackcmp(long a, long b) {
	return a < b;
}
int N, K;
int resultValue = 0;
vector<Node> jinju;
vector<long> backpack;

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

	for (int i = 0; i < N; i++) {
		int v;
		long m;
		cin >> m >> v;
		jinju.push_back({ m,v });
	}

	for (int i = 0; i < K; i++) {
		long num;
		cin >> num;
		backpack.push_back(num);
	}
	sort(jinju.begin(), jinju.end(), cmp);
	sort(backpack.begin(), backpack.end(), backpackcmp);
}


 long GameStart() {
	priority_queue<int, vector<int>, less<int>> pq;
	
	int idx = 0;
	long sum = 0;
	for (int i = 0; i < K; i++) {
		while (idx < N && backpack[i] >= jinju[idx].first) {
			pq.push(jinju[idx].second);
			idx++;
		}

		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	return sum;
}
 void Print() {
	 cout << '\n';
	 for (int i = 0; i < backpack.size(); i++) {
		 cout << backpack[i] << " ";
	 }
	 cout << '\n';

	 for (int i = 0; i < jinju.size(); i++) {
		 cout << jinju[i].second << " ";
	 }
	 cout << '\n';
 }
int main(void) {
	Input();
	cout << GameStart();
}