보석 도둑
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 42320 | 9761 | 6854 | 21.945% |
문제
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
예제 입력 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번
알고리즘 분류
추가 반례
예제 입력 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;
}
멀티셋보다 ? 멀티맵이 더 빠르다??
![백준 2083번 (럭비 클럽, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/2022/10/boj-og-1-2048x1070-1-1024x535.png)
![백준 1547번 (공, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)