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

 

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

1202번: 보석 도둑

 

문제 설명 : 

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

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

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

 

입력 : 

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

// 두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

출력 : 

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

예제 입력 : 

3 2
1 65
5 23
2 99
10
2

예제 출력 : 

164

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 보석도둑
#if 1
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#pragma warning (disable:4996)
#define MAX (300010)

using namespace std;

int N, K;
int Jewel[MAX][2];
int Bag[MAX];
long long sol;
priority_queue<int> pq;

void Input(void);
void MakeSol(void);

int main(void)
{
	scanf("%d %d", &N, &K);
	Input();
	MakeSol();
	printf("%lld\n", sol);
	return 0;
}

int Jcompare(const void * a, const void * b){
	int * aa = (int *)a;
	int * bb = (int *)b;
	return aa[0] - bb[0];
}

int Bcompare(const void * a, const void * b){
	int * aa = (int *)a;
	int * bb = (int *)b;
	return *aa - *bb;
}

void Input(void){
	register int i;
	for (i = 1; i <= N; i++){
		scanf("%d %d", &Jewel[i][0], &Jewel[i][1]);
	}
	qsort(&Jewel[1][0], N, 8, Jcompare);
	for (i = 1; i <= K; i++)
		scanf("%d", &Bag[i]);
	qsort(&Bag[1], K, 4, Bcompare);
	return;
}

void MakeSol(void){
	register int i, j;
	sol = 0;
	for (i = 1, j = 1; i <= K; i++){
		while (j <= N && (Jewel[j][0] <= Bag[i])) {
			pq.push(Jewel[j++][1]);
		}
		if (!pq.empty()) {
			sol += pq.top();
			pq.pop();
		}
	}
	return;
	}
#endif