백준(BOJ) 14501 퇴사 *

그냥 간단한 dp문제이다.

핵심은 오늘까지 일에서 번돈이 어제까지의 번 돈보다 작은경우 오늘까지 번돈의 값을 바꿔준다.

* : dp를 풀어본 사람이라면 금방 풀 수 있을것 같다.

#include <iostream>
using namespace std;
int n,a,b,r[30],mx=0;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		if (r[i - 1] + b > r[i + a - 1])
			r[i + a - 1] = r[i - 1] + b;
		if (r[i - 1] > r[i])
			r[i] = r[i - 1];
        // 오늘까지 일에서 번돈이 어제까지의 번 돈보다 작은경우 오늘까지 번돈의 값을 바꿔준다.
		if (r[i] > mx)
			mx = r[i];
	}
	printf("%d", mx);
	return 0;
}