*[백준][13904] 과제
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
문제
웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.
웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.
입력
첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.
다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.
출력
얻을 수 있는 점수의 최댓값을 출력한다.
해결방법
1. 최종 과제 제출 마지막 날짜를 입력 받을때 구해놓았다.
2. 입력 받은 과제 목록을 제출 기간을 기준으로 내림차순으로 정렬하였다.
3. 마지막 제출날짜 이전부터 시작하여 과제시작하는 순서로 최대 포인트를 주는 숙제를 풀도록 진행했다.
4. 3번과 같이 시작한 이유는 현재 날짜에 풀 수 있는 과제는 이전 날에도 풀 수가 있기 때문에 pq를 이용하여 최대 포인트를 주는 과제를 공유할 수 있게 된다. 이말은 즉슨, 5일날이 마감인 과제는 4일이 마지막이지만, 3일째 되는날에도 풀 수 가 있게 된다.
5. 따라서 최종 제출 날짜 이전부터 pq에 넣어 풀 수 있는 최대 포인트 순서로 풀게되면 정답을 구 할 수 있게 된다.
소스코드
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
struct info {
int d;
int w;
}typedef info;
bool cmp(info& a, info& b) {
return a.d > b.d;
}
int main()
{
int N;
int endDay = 0;
vector<info> infoList;
scanf("%d", &N);
priority_queue<int, vector<int>, less<int>> pq;
for (int i = 0; i < N; i++) {
int d, w;
scanf("%d %d", &d, &w);
info tmp = { d, w };
if (endDay < d) {
endDay = d;
}
infoList.push_back(tmp);
}
sort(infoList.begin(), infoList.end(), cmp);
int idx = 0;
int answer = 0;
for (int i = endDay - 1; i >= 0; i--) {
while (idx < N && i < infoList[idx].d) {
pq.push(infoList[idx].w);
idx++;
}
if (!pq.empty()) {
answer += pq.top();
pq.pop();
}
}
printf("%d\n", answer);
}결과
