Boj 1781) 컵라면
문제
설명
데드라인이 있어서 가장 보상이 좋은 문제만 고를 수가 없다. 하지만 조금만 생각을 바꾸면 간단한 그리디 정책을 떠올릴 수 있다. 바로 모든 시간대에서 최대한 꿀문제만 고르는 것이다. 증명은 간단하므로 생략한다.
이를 좀더 구체화한 전략은 다음과 같다. i
시간 이하의 문제를 그룹에 넣고, 보상에 대해 정렬했을 때 인덱스가 i
보다 큰 경우를 모두 배제한다. 시간을 i+1
로 올리고 이를 반복한다.
- 이때 우선순위 큐를 사용하면 정렬된 상태를 유지하고 크기를 일정하게 유지하는 것을 간단하게 구현할 수 있다.
- 또한 굳이 시간을
1
단위로 세지않고 데드라인 단위로 해도 된다. 데드라인이 짧은 시간부터 큐에 넣어 가장 최근에 넣은 데드라인과 큐의 크기를 비교하면 된다.
시간 복잡도
O(\(\mathrm{N}\log{\mathrm{N}}\))
코드
struct Item
{
int dead, cup;
bool operator()(const Item& a, const Item& b) { return a.cup > b.cup; }
} items[200001];
int main()
{
int n; cin >> n;
for (int i = 0; i < n; i++)
cin >> items[i].cup >> items[i].dead;
priority_queue<Item, std::vector<Item>, Item> pq;
sort(items, items + n, [](Item& a, Item& b) { return a.dead < b.dead; });
for (int i = 0, t = 0; i < n; i++)
{
pq.push(items[i]);
if (items[i].dead < pq.size())
pq.pop();
}
long long ans = 0;
while (pq.size())
{
ans += pq.top().cup;
pq.pop();
}
cout << ans;
}
댓글남기기