[BAE/<JOON> 문제풀이] 14501. 퇴사 (DP.014)

https://www.acmicpc.net/problem/14501

14501번: 퇴사

#include <iostream>
#include <vector>

using namespace std;

vector<int> time, cost, parent;
vector<int> dp;
int n;

int main() {
	cin >> n;
	time.resize(n + 1);
	cost.resize(n + 1);
	dp.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> time[i] >> cost[i];
		dp[i] = cost[i];
	}
	int mx = 0;	
	for (int i = 2; i <= n; i++) {		
		for (int j = 1; j < i; j++) {
			if (time[j] > i - j) continue;
			if (dp[i] < dp[j] + cost[i]) {
				dp[i] = dp[j] + cost[i];				
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (mx < dp[i] && i + time[i] - 1 <= n) {
			mx = dp[i];
		}
	}
	cout << mx << endl;
	return 0;
}