https://www.acmicpc.net/problem/13904
이 문제의 경우 그리디 문제이다 이 문제의 경우 Priority Queue로 풀면 쉽게 풀리는 문제였다. 일단 나는 이 문제를 보고 냅색문제 와 비슷 하다고 생각했다.
일단 나는 이문제의 숙제의 중요도를 숙제의 점수 라고 생각 했다 이에 우선순위 큐에 과제를 끝냈을 때의 점수가 가장 높은것들 순으로 나열 시켰다.
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5우리의 테스트 케이슬 중요도 즉 과제를 맞췄을 때의 점수를 해당로직대로 내림차순 정렬 하게 되면 아래 그림 처럼 된다
우리가 실제로 과제를 한다 생각 해 보자 우리는 당연히 가장 중요한걸 될 수 있는 한 최대한 미룰 것이다 즉 첫번째 4,60은 아직 4일 차에 내가 할 일이 없으므로 60에 중요도를 가진 과제를 한다.
그후 오는 2,50은 아직 2일차에 아무일도 없으므로 50에 일을 한다
그 후 4,40의 일은 4일 안에만 하면 되나 4일차에는 60의 일이 있으므로 4일보다 앞에 배정한다 그래서 3일 차에 40의 일을 한다
그후 3,30은 이미 3일차에 40의 일을 하였으니 3일안에 내가 할수 있는 요일은 1일차 밖에 없다 이에 30의 일은 1일 차에 한다
그후 1,20의 일은 이미 1일차에 30의 일을 하니 하지 않는다
그후 4,10의 일도 이미 4일 안에 진행 하는 일들은 다 중요도 가 높으므로 진행 하지않는다
그후 6,5는 6일차는 비어 있으므로 넣는다
즉 이문제의 풀이는 날짜를 최대한 미루데 중요한거를 우선 해서 리스트에 넣어야 한다 이에 만약 내가 4,40의 일을 한다고 가정했을 때 지금 업무를 완료했을 때의점수순으로 나열했기에 후에 나보다 낮은 일수가 나온다고 해도 점수가 높지 않고 일수도 낮고 점수도 낮은게 나올 수가 없으므로 빈공간에 채워주는 식으로 로직을 진행해야 한다
#include<iostream>
#include<queue>
using namespace std;
int day[1001] = {};
struct Compare {
bool operator()(pair<int, int> const& p1, pair<int, int> const& p2) {
return p1.second < p2.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;
int main() {
int N;
cin >> N;
int num1, num2;
int maxIdx=0;
int result = 0;
for (int i = 0; i < N; i++) {
cin >> num1 >> num2;
if (num1 > maxIdx) {
maxIdx = num1;
}
pq.push({ num1,num2 });
}
while (!pq.empty()) {
int x, y;
x = pq.top().first;
y = pq.top().second;
pq.pop();
if (day[x]== 0) {
day[x] = y;
}
else {
for (int i = x - 1; i > 0; i--) {
if (day[i] == 0) {
day[i] = y;
break;
}
}
}
}
for (int i = maxIdx; i > 0; i--) {
result += day[i];
}
cout << result;
}