보석 도둑  

www.acmicpc.net/problem/1202

문제

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

상덕이가 털 보석점에는 보석이 총 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

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

힌트

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

출처

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

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

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

추가 반례

예제 입력 A

10 10
1 1
6 5
8 12
10 20
15 22
23 27
26 36
27 46
35 55
42 61
1
8
17
24
31
39
40
42
51
55

예제 출력 A

285

예제 입력 B

100 500
1 1
6 9
7 12
14 19
21 23
24 32
28 39
34 45
39 49
43 58
48 59
55 60
63 69
73 71
81 80
87 90
92 98
95 102
99 105
107 109
111 114
112 118
119 124
127 128
136 132
144 133
146 135
151 145
154 146
159 150
164 155
171 162
172 172
175 173
183 174
187 183
191 185
195 190
205 200
206 202
210 208
214 209
215 212
217 214
220 217
228 227
232 234
242 236
248 237
257 241
260 251
265 260
273 267
281 268
284 271
291 275
298 280
308 288
318 296
325 304
335 313
340 314
346 317
354 324
360 327
364 329
366 332
371 334
372 344
380 347
389 348
397 351
400 354
402 361
405 365
407 374
412 381
422 382
427 383
433 392
435 400
445 409
448 412
458 418
464 428
470 435
480 436
484 438
487 444
497 449
502 450
504 451
505 459
515 469
516 478
518 483
520 486
521 493
530 500
532 503
1
7
8
17
26
35
39
48
52
56
63
64
65
73
73
80
89
98
102
104
113
120
127
130
136
137
139
148
156
163
172
180
188
193
202
202
203
203
208
213
219
219
223
226
227
230
231
234
240
246
254
255
257
258
265
274
278
283
287
289
289
289
297
302
309
313
318
323
330
336
336
345
353
356
358
363
371
373
381
384
388
388
388
393
400
403
403
406
411
418
427
429
438
442
443
449
450
454
463
464
468
477
481
481
490
491
497
506
507
513
513
520
525
525
530
537
543
543
548
556
563
569
569
578
579
588
595
602
602
605
613
619
627
631
637
639
644
647
651
655
664
671
671
676
681
685
694
701
702
709
714
716
724
731
733
742
743
746
752
761
768
776
776
782
790
797
801
805
809
810
811
814
822
823
829
832
833
833
837
838
847
856
858
858
862
862
866
866
871
880
886
886
886
886
892
895
901
902
908
911
918
924
924
930
930
935
943
952
957
962
970
977
983
990
999
1004
1007
1012
1018
1024
1027
1028
1034
1039
1048
1050
1057
1058
1066
1069
1075
1080
1082
1084
1093
1100
1101
1105
1105
1107
1109
1116
1125
1126
1127
1134
1135
1139
1140
1143
1147
1148
1154
1162
1169
1173
1180
1189
1192
1192
1195
1203
1205
1213
1220
1220
1229
1234
1236
1238
1239
1245
1249
1258
1261
1263
1271
1275
1279
1279
1287
1287
1292
1295
1303
1308
1309
1317
1317
1326
1327
1333
1336
1345
1345
1348
1356
1363
1368
1375
1378
1387
1392
1397
1406
1410
1411
1412
1419
1425
1430
1437
1438
1445
1445
1451
1460
1469
1478
1485
1491
1494
1497
1505
1513
1520
1525
1528
1534
1537
1540
1543
1547
1549
1549
1552
1560
1567
1575
1577
1580
1589
1590
1594
1595
1601
1610
1615
1620
1623
1629
1634
1636
1639
1643
1645
1650
1655
1657
1659
1665
1672
1674
1678
1682
1683
1684
1690
1699
1706
1715
1721
1727
1727
1733
1733
1736
1745
1746
1748
1753
1755
1755
1761
1763
1768
1771
1780
1787
1792
1796
1801
1803
1804
1807
1813
1820
1825
1828
1832
1837
1846
1846
1849
1853
1861
1864
1867
1876
1880
1881
1887
1891
1896
1896
1904
1907
1909
1915
1915
1920
1924
1925
1933
1933
1939
1939
1940
1948
1951
1959
1964
1970
1972
1979
1984
1988
1991
1999
2005
2013
2022
2026
2034
2042
2050
2051
2051
2060
2061
2063
2070
2072
2075
2081
2082
2084
2092
2095
2098
2105
2109
2113
2113
2115
2121
2124
2128
2136
2139
2145
2152
2152
2157
2157
2163
2170
2176
2183
2190
2190
2197
2199
2205
2210
2217
2218
2220
2225
2231
2234
2242
2248
2255
2263
2267
2271
2277
2284
2284

예제 출력 B

25259

보석점의 보석 개수 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;
}

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