Table Of Contents

보석 도둑
추가 반례
틀린 코드 1
틀린 코드 2
틀린 코드 3
통과된 코드 1
통과된 코드 2

보석 도둑

www.acmicpc.net/problem/1202

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	42320	9761	6854	21.945%

문제

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

상덕이가 털 보석점에는 보석이 총 N개 있다.

각 보석은 무게 M_i와 가격 V_i를 가지고 있다.

상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 C_i이다.

가방에는 최대 한 개의 보석만 넣을 수 있다.

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

입력

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

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

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

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

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

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #1 4번

문제를 번역한 사람: baekjoon
잘못된 조건을 찾은 사람: eeight

알고리즘 분류

추가 반례

lopov / 추가 예제 다운로드

예제 입력 A

예제 출력 A

예제 입력 B

예제 출력 B

보석점의 보석 개수 N (1 ≤ N ≤ 300,000)

각 보석은 무게 M / 가격 V

상덕이의 가방 개수 K (1 ≤ K ≤ 300,000)

각 가방에 담을 수 있는 최대 무게 C ( 1<= C <=100,000,000)

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하기

출력은 보석 가격의 합의 최대값

보석의 개수 2 가방의 개수 1
—————————————- 보석의 개수만큼

첫 번째 보석 무게 5 가치 10
두 번째 보석 무게 100 가치 100

—————————————- 가방의 개수만큼

가방에 담을 수 있는 최대 무게 11
범위가 100,000,000
가방에는 최대 한 개의 보석만 가능

음… 보석의 가치를 높은 순으로 정렬하고
가방의 허용 무게를 낮은 순으로 정렬하여 찾아보자

예제는 다 맞으나 시간 초과….
몇 가지 조건이 더 필요한 것 같다.
남아있는 보석의 최대 무게랑 남은 가방의 최대 허용 무게를 비교하면 어떨까?

틀린 코드 1

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

// 보석의 개수 N, 가방의 개수 K
int N, K, result;
// 가방의 허용 무게
int allowableWeight[];

//<보석의 가치, 보석의 무게 , 내림차순 정렬>
multimap<int, int, greater<int>> myMultimap;

//  처음 초기화 함수
void Initializaion()
{
	cin >> N >> K;

	int result = 0;
	int tempN = 0;
	int tempK = 0;

	// 보석의 개수에 따른 무게와 가치
	while (tempN < N)
	{
		int w, v;
		cin >> w;
		cin >> v;
		myMultimap.insert({v, w});
		tempN++;
	}
	
	// 가방 개수에 따른 허용 무게 데이터 입력
	while (tempK < K)
	{
		cin >> allowableWeight[tempK];
		tempK++;
	}

	// 가방을 오름차순으로 정렬
	sort(allowableWeight, allowableWeight + K);
}

void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번 씩 순회한다.
	for (auto& elem : myMultimap)
	{
		// 허용 무게가 가장 낮은 순으로 정렬된 배열을 보석마다 돌아준다.
		for (int i = 0; i < K; i++)
		{
			// 가방을 사용하거나 없을 경우를 걸러줌
			if (allowableWeight[i] != 0)
			{
				// 만약 보석의 무게가 가방의 허용 무게보다 낮으면 
				// 가방 초기화 및 결과 값에 더 해주고 반복문을 나감
				if (elem.second <= allowableWeight[i])
				{
					allowableWeight[i] = 0;
					result += elem.first;
					//반복문을 나감
					break;
				}
			}
		}
	}
}


int main()
{
	
	Initializaion();
	AlgorithmOfGreed();
	cout << result;
	return 0;
}

1. 모든 가방의 최대 무게보다 높은 보석은 가방 검색을 하지 않음

2. 모든 보석의 최소 무게보다 낮은 가방은 가방 검색을 하지 않음

틀린 코드 2

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

// 가방의 허용 무게
int allowableWeight[300001] = { 0 };

// 보석의 개수 N, 가방의 개수 K
int N, K;
unsigned long result;
int tempW, tempV;
int currentJewelHighestWeight = 0;
int maximumAllowableWeightOfCurrentBag = 0;

//<보석의 가치, 보석의 무게 , 내림차순 정렬>
multimap<int, int, greater<int>> myMultimap;

//  처음 초기화 함수
void Initializaion()
{
	cin >> N >> K;

	int result = 0;
	int tempN = 0;
	int tempK = 0;

	// 보석의 개수에 따른 무게와 가치
	while (tempN < N)
	{
		cin >> tempW >> tempV;
		myMultimap.insert({tempV, tempW});
	
		if (currentJewelHighestWeight > tempW)
		{
			currentJewelHighestWeight = tempW;
		}

		tempN++;
	}
	
	// 가방 개수에 따른 허용 무게 데이터 입력
	while (tempK < K)
	{
		// 가방의 허용 무게가 보석의 가장 가벼운 무게보다 작을 경우 제외함
		if (tempK < currentJewelHighestWeight)
		{
			continue;
		}
		cin >> allowableWeight[tempK];
		tempK++;
	}

	// 가방을 오름차순으로 정렬
	sort(allowableWeight, allowableWeight + K);
	maximumAllowableWeightOfCurrentBag = allowableWeight[K];
}

void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번씩 순회한다.
	for (auto& elem : myMultimap)
	{
		// 보석의 무게가 가방의 허용치 중에서 가장 높은 값보다 클 경우 제외
		if (elem.second < maximumAllowableWeightOfCurrentBag)
		{
			continue;
		}

		// 허용 무게가 가장 낮은 순으로 정렬된 배열을 보석마다 돌아준다.
		for (int i = 0; i < K; i++)
		{
			// 가방이 사용 됬을 경우를 알려줌
			if (allowableWeight[i] != 0)
			{
				// 만약 보석의 무게가 가방의 허용무게보다 낮으면 
				// 가방 초기화 및 결과 값에 더 해주고 반복문을 나감
				if (elem.second <= allowableWeight[i])
				{
					allowableWeight[i] = 0;
					result += elem.first;
					//반복문을 나감
					break;
				}
			}

		}
	}
}


int main()
{
	Initializaion();
	AlgorithmOfGreed();
	cout << result;
	//cout << "반복 체크";
	return 0;
}

시간 초과

가방을 300만 개 탐색에 문제가 있는 것 같음

가방을 반대로 정렬해서 확인해야 할 것 같다.

틀린 코드 3

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>

using namespace std;

//가방의 허용 무게
int allowableWeight[300000] = { 100000001 };

// 보석의 개수 N, 가방의 개수 K
int N, K;
long long result = 0;
int tempW, tempV;
int currentJewelHighestWeight = 0;
int maximumAllowableWeightOfCurrentBag = 0;

//<보석의 가치, 보석의 무게, 내림차순 정렬>
multimap<int, int, greater<int>> myMultimap;

//  처음 초기화 함수
void Initializaion()
{
	cin >> N >> K;

	int tempN = 0;
	int tempK = 0;

	// 보석의 개수에 따른 무게와 가치
	while (tempN < N)
	{
		cin >> tempW >> tempV;

		myMultimap.insert({ tempV, tempW });

		tempN++;
	}

	// 가방 개수에 따른 허용 무게 데이터 입력
	while (tempK < K)
	{
		cin >> tempW;
		allowableWeight[tempK] = tempW;
		tempK++;
	}

	// 가방을 오름차순으로 정렬
	sort(allowableWeight, allowableWeight + K);
}

/*
void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번씩 순회한다.
	for (auto& elem : myMultimap)
	{
		// 보석의 무게가 가방의 허용치 중에서 가장 높은 값보다 클 경우 제외
		if (elem.second < maximumAllowableWeightOfCurrentBag)
		{
			continue;
		}

		// 허용 무게가 가장 낮은 순으로 정렬된 배열을 보석마다 돌아준다.
		for (int i = 0; i < K; i++)
		{
			//cout << i << "\n";
			if (allowableWeight[i] == 0)
			{
				break;
			}

			cout << lower_bound(allowableWeight, allowableWeight + K, elem.second) - allowableWeight << "\n";

			// 가방이 사용 됬을 경우를 알려줌
			if (allowableWeight[i] != -1)
			{
				// 만약 보석의 무게가 가방의 허용무게보다 낮으면
				// 가방 초기화 및 결과 값에 더 해주고 반복문을 나감
				if (elem.second <= allowableWeight[i])
				{
					allowableWeight[i] = -1;
					result += elem.first;
					//반복문을 나감
					break;
				}
			}
		}
	}
}

*/
void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번씩 순회한다.
	for (auto& elem : myMultimap)
	{
		//// 보석의 무게가 가방의 허용치 중에서 가장 높은 값보다 클 경우 제외
		//if (elem.second < maximumAllowableWeightOfCurrentBag)
		//{
		//	continue;
		//}

		for (int i = (lower_bound(allowableWeight, allowableWeight + K, elem.second) - allowableWeight) ; i < K; i++)
		{
			sort(allowableWeight, allowableWeight + K);
			// 사용하지 않는 가방일 경우 패스 
			if (allowableWeight[i] >= 100000002)
			{
				break;
			}

			//cout << lower_bound(allowableWeight, allowableWeight + K, elem.second) - allowableWeight << "\n";
			
			// 가방이 사용 됬을 경우를 알려줌
			if (allowableWeight[i] != 100000001)
			{
				// 만약 보석의 무게가 가방의 허용무게보다 낮으면 
				// 가방 초기화 및 결과 값에 더 해주고 반복문을 나감
				if (elem.second <= allowableWeight[i])
				{
					//cout << "i : " << i << " allowableWeight[i] : " << allowableWeight[i] << " elem.first : " << elem.first << " elem.second : " << elem.second << "\n";
					allowableWeight[i] = 100000001;
					result += elem.first;
					//반복문을 나감
					break;
				}
			}
		}
	}
}

int main()
{
	Initializaion();
	AlgorithmOfGreed();
	cout << result;
	return 0;
}

배열을 마킹? 해주면서 순서가 꼬임

마킹 방법이 값을 변경하는 방법이라서 문제가 발생

무게를 넘어가는 값으로 변경하고 다시 정렬하려면 배열 탐색을 계속해야 하는 문제가 발생

답이 없어서 멀티맵으로 가방도 변경

통과된 코드 1

알고리즘을 생각하는 시간보다는 C++ 컨테이너 사용법에 시간이 더 많이 소모

멀티맵, 반복자 사용법 등 다양한 고난이 있었다.

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

// 보석의 개수 N, 가방의 개수 K
int N, K;

// 결과 값의 범위가 int의 최대 범위를 넘어갈 수 있음
long long result = 0;

//<보석의 가치, 보석의 무게, 내림차순 정렬>
multimap<int, int, greater<int>> jewelryMultimap;

// <가방의 무게 , 사용 체크>
// 사용 체크는 사용을 안하지만 멀티맵 형식 때문에 사용
multimap<int, bool> bagMultimap;
//허용 무게가 낮은 순서대로 정렬된 가방

// 반복자 선언
multimap<int, bool>::iterator it;


//  처음 초기화 함수
void Initializaion()
{
	cin >> N >> K;

	int tempW = 0;
	int tempV = 0;
	int temp = 0;

	// 보석의 개수에 따른 무게와 가치
	while (temp < N)
	{
		cin >> tempW >> tempV;
		jewelryMultimap.insert({ tempV, tempW });
		temp++;
	}
	temp = 0;

	// 가방 개수에 따른 허용 무게 데이터 입력
	while (temp < K)
	{
		cin >> tempW;
		bagMultimap.insert({tempW, false});
		temp++;
	}
}

void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번씩 순회한다.
	for (auto& elem : jewelryMultimap)
	{
	    // 허용 무게가 낮은 순으로 정렬된 가방들
		// 가방 중에서 보석의 무게 이상의 값 중 가장 가까운 값을 찾음
		for (it = bagMultimap.lower_bound(elem.second);it != bagMultimap.end(); it++)
		{
			//해당 가방을 찾으면 결과 값에 가치를 더하고
			result += elem.first;
			// 해당 가방을 지움
			// bool 체크로 하려고 했으나 시간초과
			bagMultimap.erase(it);
			break;
		}
	}
}

int main()
{
	// 초기화
	Initializaion();
	// 그리드 알고리즘
	AlgorithmOfGreed();
	cout << result;
	return 0;
}

multiset을 사용하는 것이 좋은 것 같아서 교체

통과된 코드 2

#include <iostream>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

// 보석의 개수 N, 가방의 개수 K
int N, K;

// 결과 값의 범위가 int의 최대 범위를 넘어갈 수 있음
long long result = 0;

//<보석의 가치, 보석의 무게, 내림차순 정렬>
multimap<int, int, greater<int>> jewelryMultimap;

// <가방의 무게 , 사용 체크>
// 사용 체크는 사용을 안하지만 멀티맵 형식때문에 사용
multiset<int> bagMultiset;
//허용 무게가 낮은 순서대로 정렬된 가방

// 반복자 선언
multiset<int>::iterator it;


//  처음 초기화 함수
void Initializaion()
{
	cin >> N >> K;

	int tempW = 0;
	int tempV = 0;
	int temp = 0;

	// 보석의 개수에 따른 무게와 가치
	while (temp < N)
	{
		cin >> tempW >> tempV;
		jewelryMultimap.insert({ tempV, tempW });
		temp++;
	}
	temp = 0;

	// 가방 개수에 따른 허용 무게 데이터 입력
	while (temp < K)
	{
		cin >> tempW;
		bagMultiset.insert(tempW);
		temp++;
	}
	// 가방을 오름차순으로 정렬
}

void AlgorithmOfGreed()
{
	// 가치가 높은 순서대로 정렬된 보석들을 한번씩 순회한다.
	for (auto& elem : jewelryMultimap)
	{
	    // 허용 무게가 낮은 순으로 정렬된 가방들
		// 가방중에서 보석의 무게 이상의 값중 가장 가까운 값을 찾음
		for (it = bagMultiset.lower_bound(elem.second);it != bagMultiset.end(); it++)
		{
			//해당 가방을 찾으면 결과값에 가치르 더하고
			result += elem.first;
			// 해당 가방을 지움
			// bool 체크로 하려고 했으나 시간초과뜸
			bagMultiset.erase(it);
			break;
		}
	}
}

int main()
{
	// 초기화
	Initializaion();
	// 그리드 알고리즘
	AlgorithmOfGreed();
	cout << result;
	return 0;
}

멀티셋보다 ? 멀티맵이 더 빠르다??

백준 1202번 (보석 도둑, C++, Greedy) / 추가 반례 [BAEKJOON]

보석 도둑

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

출처

알고리즘 분류

추가 반례

예제 입력 A

예제 출력 A

예제 입력 B

예제 출력 B

틀린 코드 1

틀린 코드 2

틀린 코드 3

통과된 코드 1

통과된 코드 2

댓글 달기 댓글 취소

보석 도둑

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

출처

알고리즘 분류

추가 반례

예제 입력 A

예제 출력 A

예제 입력 B

예제 출력 B

틀린 코드 1

틀린 코드 2

틀린 코드 3

통과된 코드 1

통과된 코드 2

댓글 달기 댓글 취소

관련 게시물