문제 이해 단계
문제 이해 자체는 크게 어렵지 않다.
얻을 수 있는 돈 p와 날짜 제한인 d가 들어온다.
강연을 하나 할 때마다 1일씩 소모되는데, 이 조건에서 얻을 수 있는 최대 값을 구하는 것이다.
문제 접근 단계
이 문제는 최댓값을 구하는 문제이기 때문에
당연히 얻는 돈이 큰 수를 최대한 뽑는 것이 중요하다.
하지만 시간제한이 존재하기 때문에
같은 시간제한을 가진 강연은 뽑는 것이 제한된다.
예를 들어 (30,1), (20,1)이 있을 경우, 둘 중 하나밖에 고르지 못하는 것이다.
여기선 당연히 (30,1)을 고르는 것이 최선이다.
그래서 나는 이 수들을 내림차순 정렬하여 큰 수를 넣는데,
가능한 조합만 고르려고 하니까 시간초과가 뜰 것 같았다.
그래서 우선순위 큐를 이용하여 값을 넣어주어
제일 작은 값과 다음 값을 비교하여, 갈아 끼우는 방식을 사용했다.
여기서 중요한 것은 시간제한을 고려하여 큐에 넣어야 한다는 것이다.
나는 이를 시간제한을 기준으로 오름차순으로 정렬 한 뒤,
시간이 촉박한(d가 더 작은)것부터 넣어, 큐에 들어간 개수를 기준으로 값을 구성하였다.
이러한 방식을 사용하면 d = 1인 것들을 먼저 넣어, 이 수 중 가장 큰 값이 큐에 남게 한다.
이후, d = 2인 것들을 넣고 큐 안에 들어간 것 중
가장 작은 값이 빠지는 방식을 반복한다.
문제 구현 단계
vector<pair<int, int>> v;
priority_queue<int, vector<int>, compare> q;
while (n-- > 0) {
cin >> p >> d;
v.push_back(make_pair(d, p));
}
sort(v.begin(), v.end());
q.push(v[0].second);
for (int i = 1; i < v.size(); i++) {
if (v[i].first > q.size()) q.push(v[i].second);
else {
if (v[i].second > q.top()) {
q.pop();
q.push(v[i].second);
}
}
}입력들을 d를 기준으로 오름차순 정렬해 줄 벡터와 우선순위 큐를 만들었다.
나는 여기서 (d, p) 쌍으로 원래 입력과는 뒤집어서 저장하였다.
벡터에서 d가 가장 낮은 값을 넣어주는데
넣어줄 때마다 큐의 사이즈보다 큰지를 확인한다.
이렇게 해주는 이유는 만약 (1,10)이 들어온다고 치면
큐에는 최대 하나밖에 들어오지 못한다.
하지만 (3,10)인 경우에는 최대 3번째 즉, d = 3인 값이 최대 3개 들어올 수 있다.
이를 큐 안에 들어있는 개수로 나타낼 수 있다.
즉, 큐 안에 들어가 있는 개수보다 d가 크다면, 순서가 맞기 때문에 넣을 수 있다.
그렇기 때문에 큐에 넣어주기만 하면 된다.
그렇지 않을 경우에만 큐에 가장 위쪽에 있는 값(가장 작은 값)과 비교하여
그 값보다 클 경우 교체해 주는 작업을 해준다.
이 과정을 반복하면 큐에는 시간제한에 맞는 수 들 중에서 가장 큰 값들만 남게 된다.
int ans = 0;
while (!q.empty()) {
ans += q.top();
q.pop();
}
cout << ans;그 후 이 값들을 모두 더해주면 얻을 수 있는 최댓값을 구 할 수 있다.
마지막으로 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
struct compare {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
int n, p, d;
cin >> n;
if (n == 0) {
cout << "0";
return 0;
}
vector<pair<int, int>> v;
priority_queue<int, vector<int>, compare> q;
while (n-- > 0) {
cin >> p >> d;
v.push_back(make_pair(d, p));
}
sort(v.begin(), v.end());
q.push(v[0].second);
for (int i = 1; i < v.size(); i++) {
if (v[i].first > q.size()) q.push(v[i].second);
else {
if (v[i].second > q.top()) {
q.pop();
q.push(v[i].second);
}
}
}
int ans = 0;
while (!q.empty()) {
ans += q.top();
q.pop();
}
cout << ans;
return 0;
}
시행착오
해당 문제는 그래도 수월하게 풀었는데,
우선순위 큐의 개념을 어느 정도 알고 있었기 때문이다.
오름차순으로 정렬한 수를 다시 한번 정렬해야 한다는 발상을
떠올리기는 조금 어려웠지만 그래도 어느 정도 풀만했던 문제 같다.
아니면 내가 우선순위큐에는 강한 걸지도 모르겠다.