| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 3028 | 999 | 764 | 34.508% |
문제
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
접근
최근 너무 자주 푼 그리디 유형의 문제였다.
날짜의 끝에서부터 순회하면서 우선순위큐를 활용하여 최댓값을 추가해주면 된다.
풀이
arr를 시간순으로 정렬한 뒤 투 포인터로 맨 뒤부터 접근한다.
시간을 최댓값부터 뒤에서 순회하면서,
현재 시간 이상의 값을 가지는 arr의 금액을 pq에 넣어준다.
pq가 비어있지 않으면, top 값을 answer에 더해준다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N;
ll ans = 0;
pair<int, int> arr[10000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(N);
FUP(i, 0, N - 1) CIN2(arr[i].second, arr[i].first);
sort(arr, arr + N);
int idx = N - 1;
priority_queue<int> pq;
FDOWN(t, arr[N - 1].first, 1)
{
while (idx >= 0 && arr[idx].first >= t)
{
pq.push(arr[idx--].second);
}
if (!pq.empty())
{
ans += pq.top();
pq.pop();
}
}
COUT(ans);
return 0;
}
Beginner