[백준] 13904 과제

과제를 하루에 하나씩 할 수 있고 , 데드라인과 받을 수 있는 점수를 알려준다

이 때 점수의 최댓값을 구하는 문제!

흔히 볼 수 있는 dp문제다

우리는 과제를 하나하나 보며 선택하면 된다!

d[N(n번째 과제)][T(현재시간)]로 테이블을 잡는다

기본값은 과제를 안하고 넘어가는 값으로 잡는다

그리고 만약 현재의 과제 데드라인보다 시간이 작다면 과제를 하는것과 비교한다!

소스코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n,d[1010][1010];
vector<pair<int, int>> vt;
int go(int pos, int t) {
    if (pos == n || t > 1000) return 0;
    int&ret = d[pos][t];
    if (ret != -1) return ret;
    int ptime = vt[pos].first;
    int pcost = vt[pos].second;
    ret = max(ret, go(pos + 1, t));
    if (t <= ptime) ret = max(ret, go(pos + 1, t + 1) + pcost);
    return ret;
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d", &n);
    vt.resize(n);
    for (int i = 0; i < n; i++) scanf(" %d %d", &vt[i].first, &vt[i].second);
    sort(vt.begin(), vt.end());
    printf("%d\n", go(0, 1));
}