일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- BFS
- 재귀
- 세그먼트트리
- 알고리즘문제해결전략
- 너비우선탐색
- DFS
- BOJ
- 누적합
- 동적계획법
- priority_queue
- 스택
- 알고스팟
- 분리집합
- Algospot
- acm
- 분할정복
- 백트래킹
- stack
- backtracking
- 문자열
- 이분탐색
- union-find
- 완전탐색
- 그리디
- Greedy
- 유니온파인드
- 다이나믹프로그래밍
- 백준
- 종만북
- DP
- Today
- Total
DAMPER's 낙서장
1202 보석 도둑 본문
처음에 이 문제를 보고 바로 동전DP를 떠올렸지만, 각 가방에 한 개의 보석만 넣을 수 있고, 각각의 가방에 넣을 수 있는 보석의 무게가 다르기 때문에 조금 다른 문제라 생각했다.
풀이 방법
용량이 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다.
예를들어, 아래와 같은 상황이라고 하자.
먼저 가방 용량을 오름차순으로 정렬하고, 보석을 무게를 기준으로 오름차순으로 정렬한다.
용량이 가장 작은 5부터 보석을 넣는다고 하면,
빨간색인 4가지 보석들을 넣을 수 있다.
이 때, 가장 가치가 큰 보석을 하나 넣으면 된다.
여기서 이미 무게를 기준으로 정렬되어있는 보석을, 다시 가치를 기준으로 정렬을 해야하는 상황이 발생한다.
그러면서 다음 가방에 넣을 보석들은 다시 무게를 기준으로 정렬되어있어야 어떤 보석은 넣을 수 있고, 없는지를 빠르게 판단할 수 있다.
이런 상황에서 문제를 해결할 수 있는 기법은 정형화 되어있으니, 다른 문제를 풀 때 이 방법을 기억하자.
바로 우선순위 큐를 이용한 방법이다.
용량이 작은 가방부터 시작해서 해당 가방 용량에 넣을 수 있는 보석들을 모두 우선순위 큐 안에 넣는다.
(이 때, 보석을 어디까지 넣었는 지 인덱스를 저장해서 다음에 사용해야한다.)
우선순위 큐 안에 들어있는 모든 보석들은 해당 가방에 넣을 수 있으므로, 우선순위 큐에서 가장 큰 가치를 가진 보석을 꺼내 answer 값에 더한다.
다음 가방에서도 동일하게 적용하는데, 다음 가방은 이전 가방보다 용량이 크므로 지금 우선순위 큐 안에 들어있는 모든 보석들은 해당 가방에 넣을 수 있다.
이것을 기반으로 우선순위 큐 안에 더 넣을 보석이 있으면 넣고, 우선순위 큐에서 하나 더 꺼내 answer 값에 더한다.
위 과정을 반복하면 해답을 찾을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
vector<pair<lld, lld>> mv(n);
vector<lld> c(k);
for(int i=0;i<n;i++)
cin >> mv[i].first >> mv[i].second;
for(int i=0;i<k;i++)
cin >> c[i];
sort(mv.begin(), mv.end());
sort(c.begin(), c.end());
lld ans = 0LL;
int idx = 0;
priority_queue<lld, vector<lld>, less<lld>> pq;
for(int i=0;i<k;i++)
{
while(idx<n && mv[idx].first<=c[i])
{
pq.push(mv[idx++].second);
}
if(pq.size())
{
ans += pq.top();
pq.pop();
}
}
cout << ans;
return 0;
}
|
cs |
'Problem Solving > BOJ 문제풀이' 카테고리의 다른 글
4779 칸토어 집합 (0) | 2021.05.05 |
---|---|
6064 카잉 달력 (0) | 2021.04.29 |
16928 뱀과 사다리 게임 (0) | 2021.04.26 |
9019 DSLR (0) | 2021.04.25 |
5525 IOIOI (0) | 2021.01.11 |