[c++/백준] 14501번: 퇴사

문제 링크

14501번: 퇴사

풀이

dp 문제

1. 보통의 dp문제는 처음 인덱스부터지만, 이 문제는 마지막 인덱스부터 생각해야 한다.
   처음부터 구하면 어느 인덱스에서 온 값인지 구해야 하지만, 마지막부터 생각하면 단순화할 수 있기 때문.
2. 해당 날짜에 상담을 할지 vs 안할지 값을 비교해 갱신해주면 된다.
3. i+t[i]가 n보다 크다면 범위를 넘으므로 dp[i+1을 해준다. 이 값을 위해 dp를 n+1 사이즈로 만들었고 dp[n]을 0으로 초기화해주었다.
   3-1. 범위를 넘지 않는다면 해당 날짜에 상담을 하는 값(dp[i+t[i]])과 상담을 안하는 값 dp[i+1] 값을 비교해 큰 쪽으로 갱신해준다.
   3-2. dp가 완성되면 dp[0]에는 최댓값이 만들어져있을 것이다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void)
{
	int n;
	cin >> n;

	vector<int> t(n);
	vector<int> p(n);
	for (int i = 0; i < n; i++)
	{
		cin >> t[i] >> p[i];
	}

	vector<int> dp(n+1);

	dp[n] = 0;

	for (int i = n - 1; i >= 0; i--)
	{
		if (i + t[i] > n) dp[i] = dp[i + 1];
		else
		{
			dp[i] = max(dp[i + t[i]] + p[i], dp[i + 1]);
		}
	}

	cout << dp[0];

	return 0;
}