💛V [백준 15486/C++] 퇴사 2

BOJ 문제 보기

---

#include <iostream>
using namespace std;

int dp[1500001];

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	// input & init
	int n;
	cin >> n;

	int pay = 0;

	for (int i = 0; i < n; i++) 
	{
		int t, p;
		cin >> t >> p;

		// solve
		pay = max(pay, dp[i]);

		if (i + t > n) continue;
		dp[i + t] = max(dp[i + t], pay + p);
	}

	// output
	cout << max(pay, dp[n]);

	return 0;
}