[14501] 퇴사

풀이

dp[i] = i일 째에 얻을 수 있는 최대 이익 = max(i번째 날에 끝날 수 있는 일 + 이 일이 시작되기 전에 얻을 수 있는 최대 이익)
dp[d] = max(dp[d], dp[curr - 1] + point[curr]);
point[i] = i번째 일에 시작하는 날짜의 일을 했을 때 얻을 수 있는 이익
vector[i].push_back(j) : 시작 날짜가j인 일이 i 번째 일에 끝날 수 있으면 PUSH
curr : for(curr : vector[i])

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > v(16,vector<int>());
int point[16];
int dp[16];
int main(void) {
	int n = 0;
	scanf("%d", &n);
	for (int d=1; d<=n; d++){
		int t = 0, p = 0;
		scanf("%d%d", &t, &p);
		point[d] = p;
		if(d+t-1 <=n) v[d + t - 1].push_back(d);
	}
	for (int d = 1; d <= n; d++) {
		dp[d] = dp[d - 1];
		for (int i = 0; i< v[d].size(); i++) {
			int curr = v[d][i];
			dp[d] = max(dp[d], dp[curr - 1] + point[curr]);
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}