[BOJ]1202번: 보석 도둑 (c++)

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

1202번: 보석 도둑

 

그리디 + BST

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct jewel {
	int weight, value;
};

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

	// 입력
	int N, K;
	cin >> N >> K;
	vector<jewel> jewels(N);
	multiset<int> bags;
	for (int i = 0; i < N; ++i)
	{
		cin >> jewels[i].weight >> jewels[i].value;
	}
	for (int i = 0; i < K; ++i)
	{
		int bag;
		cin >> bag;
		bags.insert(bag);
	}

	// 보석 가치를 기준으로 내림차순 정렬
	sort(jewels.begin(), jewels.end(), [](jewel& A, jewel& B) {

		return A.value > B.value;
		});

	/*
		1. 가장 비싼 보석부터 탐색
		2. 보석의 무게보다 같거나 큰 최소의 가방무게 찾기 -> sum 더하기
		3. 해당 가방 지우기
	*/
	long long sum = 0;
	for (auto iter = jewels.begin(); iter != jewels.end(); ++iter)
	{
		auto it_bag = bags.lower_bound(iter->weight);

		if (it_bag != bags.end())
		{
			sum += iter->value;
			bags.erase(it_bag);
		}
	}

	cout << sum;

	return 0;
}

 

대표적인 그리디 문제중 하나이다.

 

 

TIP1_자료형

 

문제 풀이의 기본 아이디어는 위의 주석내용과 같다. 

1. 가장 비싼 보석부터 탐색

2. 보석의 무게보다 같거나 큰 최소의 가방무게 찾기 -> sum 더하기

3. 해당 가방 지우기

 

2번 + 3번 때문에 이분탐색트리(BST)가 필요하다. 

조건에 맞는 요소를 찾고 + 그 위치값으로 지우기도 수행해야하기 때문이다.

c++의 set/multiset은 내부적으로 균형이진트리(AVL)로 구현되어 있으며,

탐색, 삽입, 삭제 모두 O(log N)의 시간복잡도를 보장한다고 한다.

 

위 문제의 경우, 같은 무게의 가방이 여러개가 있을 수 있기 때문에, set이 아닌 multiset이 필요하다

 

덧)

처음에는 벡터로 구현했는데 계속해서 시간초과가 났다.

왜냐면 2번의 시간복잡도 O(log K) + 3번의 시간복잡도 O(K)가 N번 일어나기 때문에...

(1 ≤ N, K ≤ 300,000)

총 O(N*K), 최대 O(900억)이 되어버리기 때문에 시간초과가 날수밖에 없다 ㅜㅜ

 

 

 

TIP2_자료형2

N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

보석의 무게는 K*Vi의 합이고 최대 300,000 * 1,000,000 이기 때문에

합계는 int의 범위를 넘을 수 있다.

따라서 long long형이 필요하다. 

 

 

 

도움을 얻은 페이지들

Binary Search Tree Implementation in C++ STL?

 

AVL Tree

multiset - C++ Reference