[ C++ 백준 1202 ] 보석 도둑
2023. 10. 25. 11:09ㆍ알고리즘/백준 문제풀이
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
일단 문제를 풀어보기로 했다.
일단 한 번 코드를 작성해보았는데, 문제가 많았다.
#include <iostream>
#include <algorithm>
using namespace std;
struct Gem
{
public:
Gem() : weight(0), price(0) {};
Gem(int weight, int price) : weight(weight), price(price) { };
~Gem() {};
public:
int weight;
int price;
bool operator>(const Gem& gem)
{
return price > gem.price;
}
};
Gem gems[300000];
int bagWeight[300000]; //가방에 담을 수 있는 최대 무게
bool visited[300000];
int gemCnt, bagCnt;
// N이 보석의 정보를 담는 개수
// K가 가방에 담을 수 있는 최대 무게
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int gemWeight, gemPrice;
cin >> gemCnt >> bagCnt;
for (int i = 0; i < gemCnt; ++i)
{
cin >> gemWeight >> gemPrice;
gems[i] = { gemWeight, gemPrice };
}
for (int i = 0; i < bagCnt; ++i)
cin >> bagWeight[i];
// 가격이 가장 높은 걸 기준으로
// 제일 무게가 적게 나가는 걸로
sort(gems, gems + gemCnt,
[](Gem a, Gem b) -> bool
{
return a > b;
});
sort(bagWeight, bagWeight + bagCnt);
int answer = 0;
for (int i = 0; i < gemCnt; ++i)
{
//가격이 비싼 보석부터 담는다.
for (int j = 0; j < bagCnt; ++j)
{
if (visited[j]) continue;
if (bagWeight[j] < gems[i].weight) continue;
visited[j] = true;
answer += gems[i].price;
break;
}
}
cout << answer;
}
시간 초과가 난 첫번째 코드다.
이중 포문으로 인해 시간도 매우 오래걸리고, 코드에서도 문제가 좀 많다.
그리고 우선순위 큐를 이용해서 문제들을 해결해보기로 했고, 코드를 작성했다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Gem
{
public:
Gem() : weight(0), price(0) {};
Gem(int weight, int price) : weight(weight), price(price) { };
~Gem() {};
public:
int weight;
int price;
bool operator<(const Gem& gem)
{
return weight < gem.weight;
}
};
Gem gems[300000];
int bagWeight[300000]; //가방에 담을 수 있는 최대 무게
priority_queue<int, vector<int>, less<int>> pq;
int gemCnt, bagCnt;
// N이 보석의 정보를 담는 개수
// K가 가방에 담을 수 있는 최대 무게
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int gemWeight, gemPrice;
cin >> gemCnt >> bagCnt;
for (int i = 0; i < gemCnt; ++i)
{
cin >> gemWeight >> gemPrice;
gems[i] = { gemWeight, gemPrice };
}
for (int i = 0; i < bagCnt; ++i)
cin >> bagWeight[i];
sort(gems, gems + gemCnt);
sort(bagWeight, bagWeight + bagCnt);
int idx = 0;
long long answer = 0;
//무게가 낮은 가방부터 체크
for (int i = 0; i < bagCnt; ++i)
{
// 무게가 낮은 보석부터 체크
while(idx < gemCnt
&& bagWeight[i] >= gems[idx].weight)
{
pq.push(gems[idx++].price);
}
if (pq.empty()) continue;
answer += pq.top();
pq.pop();
}
cout << answer;
}
해결한 코드이다.
answer를 long long 변수로 변경했고,
풀이 방식을 살짝 바꿨다.
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[ C++ 백준 17404 ] RGB 거리 2 (0) | 2023.11.02 |
---|---|
[ C++ 백준 2342 ] Dance Dance Revolution (0) | 2023.10.31 |
[ C++ 백준 1644 ] 소수의 연속합 (1) | 2023.10.24 |
[ C++ 백준 2473 ] 세 용액 (1) | 2023.10.22 |
[ 백준 ] solved.ac 플레 도전기 (0) | 2023.10.19 |