[C++] 백준(BOJ) - 1781 : 컵라면
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
| 문제 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 데드라인 | 1 | 1 | 3 | 3 | 2 | 2 | 6 | |
| 컵라면 수 | 6 | 7 | 2 | 1 | 4 | 5 | 1 |
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작은 자연수이다.
입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.
출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.
알고리즘
- 우선순위큐
- 그리디
풀이
- 데드라인이 존재 하는 문제
- 배치
- 데드라인 기반 오름차순 정렬을 한 후, size로 비교
- 배치에 대한 로직을 생각할 필요가 없다
- 최대를 만드는 방법
- 최소를 최소로
- 최대를 최대로
코드
// BOJ-1781 : 컵라면
#include<bits/stdc++.h>
using namespace std;
int n, d, p, res;
vector<pair<int, int>> v;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> d >> p;
v.push_back({ d,p });
}
sort(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙
for (int i = 0; i < n; i++)
{
pq.push(v[i].second);
if (pq.size() > v[i].first) pq.pop(); // 가방의 Capacity보다 더 큰 값이 들어오게 된다면 최소 값을 빼버림
}
while (!pq.empty())
{
res += pq.top();
pq.pop();
}
cout << res << '\n';
return 0;
}
평가
- 아이디어를 기반으로 로직을 짜고, 그 로직을 통해 코드를 일단 짜가기
- 그리디하게 접근하는 방식을 항상 먼저 생각해보기
