이번에는 백준 1781번 컵라면 문제를 풀어보았습니다.
문제를 처음 봤을 때 데드라인 안에서 최대한 많은 컵라면을 받을 수 있도록 문제를 선택해야 한다고 생각했습니다.
모든 문제를 데드라인 기준으로 정렬한 뒤, 현재까지 선택한 문제들 중 컵라면 개수가 가장 작은 문제를 언제든 제외할 수 있도록 우선순위 큐를 이용하여 구현하였습니다.
문제 설명
각 문제에는
- 데드라인
- 컵라면 개수
가 주어집니다.
한 문제를 푸는 데에는 1시간이 걸리며, 데드라인을 넘기면 컵라면을 받을 수 없습니다.
받을 수 있는 컵라면의 최대 개수를 구하는 문제입니다.
풀이 아이디어
먼저 모든 문제를 데드라인 기준으로 오름차순 정렬하였습니다.
현재 문제를 풀기로 결정하면 우선 우선순위 큐에 컵라면 개수를 넣었습니다.
만약 현재까지 선택한 문제의 개수가 현재 문제의 데드라인보다 많아진다면, 모든 문제를 수행할 수 없게 됩니다.
이 경우에는 지금까지 선택한 문제들 중 컵라면 개수가 가장 작은 문제를 제거하였습니다.
이 과정을 반복하면 항상 현재까지 가능한 문제들 중 가장 많은 컵라면을 받을 수 있는 문제들만 남게 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<pair<int, int>> inp;
int n;
cin >> n;
for (int i=0; i<n; i++) {
int d,c;
cin >> d >> c;
inp.push_back({d,c});
}
sort(inp.begin(), inp.end());
priority_queue<int, vector<int>, greater<int>> pq;
for (auto [d,p] : inp) {
pq.push(p);
if (pq.size() > d) {
pq.pop();
}
}
int ret=0;
while(!pq.empty()) {
ret += pq.top();
pq.pop();
}
cout << ret << '\n';
return 0;
}풀이 흐름
- 문제를 입력받습니다.
- 데드라인 기준으로 오름차순 정렬합니다.
- 현재 문제를 우선 선택하여 우선순위 큐에 넣습니다.
- 현재까지 선택한 문제 개수가 데드라인보다 많아지면 컵라면이 가장 적은 문제를 제거합니다.
- 모든 문제를 처리한 뒤 우선순위 큐에 남아있는 컵라면 개수를 모두 더합니다.
- 결과를 출력합니다.
구현 포인트
1. 데드라인 기준 정렬
먼저 문제를 데드라인 기준으로 오름차순 정렬하였습니다.
sort(inp.begin(), inp.end());데드라인이 빠른 문제부터 차례대로 처리하도록 구현하였습니다.
2. 최소 힙 사용
현재까지 선택한 문제들의 컵라면 개수를 최소 힙으로 관리하였습니다.
priority_queue<int, vector<int>, greater<int>> pq;컵라면 개수가 가장 작은 문제를 빠르게 제거하기 위해 최소 힙을 사용하였습니다.
3. 현재 문제 선택
현재 문제는 우선 수행한다고 가정하고 우선순위 큐에 넣었습니다.
pq.push(p);이후 현재까지 수행 가능한 문제 개수를 확인하였습니다.
4. 데드라인 초과 시 제거
현재까지 선택한 문제 개수가 현재 문제의 데드라인보다 많다면 모든 문제를 수행할 수 없습니다.
if (pq.size() > d) {
pq.pop();
}이 경우 컵라면 개수가 가장 작은 문제를 제거하여 항상 최적의 선택만 남도록 하였습니다.
5. 최종 컵라면 계산
모든 문제를 처리한 뒤 우선순위 큐에는 수행할 문제들만 남게 됩니다.
while(!pq.empty()) {
ret += pq.top();
pq.pop();
}남아있는 컵라면 개수를 모두 더하여 받을 수 있는 최대 컵라면 개수를 구하였습니다.
