[백준 - 1202] 보석 도둑

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long int integer;
typedef long long int price;

int i;
int main()
{
	integer N, K;
	scanf("%lld %lld", &N, &K);

	//fisrt = 무게, second = 가격
	vector<pair<integer, price>> jewels;
	integer M, V;
	for (i = 0; i < N; ++i)
	{
		scanf("%lld %lld", &M, &V);
		jewels.push_back(make_pair(M, V));
	}
	sort(jewels.begin(), jewels.end());

	vector<integer> C;
	integer temp;
	for (i = 0; i < K; ++i)
	{
		scanf("%lld", &temp);
		C.push_back(temp);
	}
	sort(C.begin(), C.end());

	priority_queue<price> pq;

	integer index = 0;
	integer result = 0;
	for (const auto & bag : C)
	{
		while (index < N && jewels[index].first <= bag)
		{
			pq.push(jewels[index++].second);
		}

		if (pq.empty() == false)
		{
			result += pq.top();
			pq.pop();
		}
	}
	
	printf("%lld", result);
	return 0;
}

---

||사용 기법

• 우선순위 큐

---

||풀면서 느낀 것

• 이미 알고있는 알고리즘을 생각하지 못함

이번은 우선순위큐(pq)가 핵심이였는데 이전에 사용했음에도 불구하고 pq가 생각이 나지 않았다.

대부분 기본적인 컨테이너 (리스트, 배열)정도만을 이용하여 loop으로 항상 풀어와서

이번에도 이런 식으로 해결하려다 망했다

(결정 적으로 이거때문에 시간이 많이 잡아먹음)

 

좀 더 내가 알고 있는 알고리즘을 다 생각해 보고 점차 어디에 사용해야할지 생각하는 습관을 길러야겠다.

 

• 테스트 케이스를 끝까지 보기

테스트 케이스를 하나만 보고 문제를 이해하여 정확한 문제를 파악하지 못함

모두 보고 확실히 이해 할 것

 

• 컨테이너를 사용 할때 empty 꼭 확인하기

이번에 Double Free 에러가 나왔었는데 pq가 empty일때 push를 하는 예외처리를 하지 않아 그랬었다.

다음부터는 꼭 주의하기

• 각 변수의 자료형의 최대 크기 계산하기

항상 눈대중으로 이정도면 넉넉하겠지 하고 이번에 각 변수의 자료형때문에 시간을 좀 잡아먹었다.

꼭 최대로 나올수 있는 크기 확인해야함!

---

||새로 알게 된것

• stl::vector의 capacity와 초기화 값 설정하기

//100,000크기로 할당 받고 모든 인덱스에 값을 5로 초기화 한다.
vector<int> test (100'000, 5);

항상 이렇게 하면 되지 않을까 하다가 이번에 직접해보고 작동하는걸 확인했다