문제 설명
웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.
웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.
https://www.acmicpc.net/problem/13904
제한 사항
풀이
문제를 요약하면, 주어진 과제들을 하루에 하나씩 적절히 풀어 얻은 점수의 최댓값을 구해야 한다.
해당 문제를 처음에는 DP로 접근했었다.
i번째 과제를 j번째 날에 해결했을 때 얻을 수 있는 최대 점수를 기록했다.
이렇게 진행하면 i번째 과제를 제외한 j-1번째 날의 최대 점수에서 i번째 과제 점수를 더하면 된다.
단, j-1번째 날의 점수에 자신의 과제 점수가 더해져 있는지 판단하기 위해 시간이 더 걸리기 때문에 시간초과가 발생한다.
따라서, 다른 접근법이 필요하다.
우선 직감적으로 발견할 수 있는 특징은 최대 점수를 우선적으로 처리해야 한다는 것이다.
점수가 낮은 과제를 먼저 수행하여 최대 점수를 얻기는 쉽지 않기 때문이다.
하지만 고려해야 할 부분은 점수만을 기준으로 과제를 선택한다면 충분히 처리가 가능한 과제를 무시하고 진행할 수 있다.
7
4 60
2 50
4 40
3 30
1 20
4 10
6 5위의 입력은 점수를 기준으로 정렬을 한 상태이다.
이때, 3번째 [4, 40]을 3일에 처리한다고 하면 [3, 30]은 충분히 처리할 수 있는 과제지만 무시하게 되어 정답을 구할 수 없다.
그렇다면, 점수가 큰 순서대로 정렬이 되어 있기 때문에 이후 과제들보다 높은 점수를 받는다는 것은 확정된 상태이기 때문에 마감일 이전에 처리할 수 있다고 하면 무조건 선택한다고 할 수 있다.
즉, [3, 30]을 해결한다면 [1, 20], [4, 10] 보다는 높은 점수를 받을 수 있기 때문에 3일 이전인 1~2일에 처리할 수 있다면 무조건 처리하면 된다는 뜻이다.
정리하자면, 점수순으로 정렬한 뒤 마감일 이전에 처리할 수 있는 과제를 무조건 선택하면 된다.
그리고 선택한 과제를 처리한 날짜에 과제 처리 여부를 기록하고 해당 과제의 점수들을 모두 더하면 정답을 구할 수 있다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> Tasks;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cin >> N;
vector<bool> days(1001, false);
for (int i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
Tasks.push_back({ a,b });
}
sort(Tasks.begin(), Tasks.end(), [](auto& a, auto& b) -> bool
{
return a.second > b.second;
});
int ans = 0;
for (auto& [deadline, score] : Tasks)
{
for (int i = deadline; i > 0; i--)
{
if (days[i] == false)
{
days[i] = true;
ans += score;
break;
}
}
}
cout << ans;
return 0;
}