[백준] 퇴사 2 15486번 C++ 풀이

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

15486번: 퇴사 2

#include <iostream>
#include <algorithm>
using namespace std;
int T[1500001];
int P[1500001];
int dp[1500051];
int N,res=0;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> T[i] >> P[i];

	for (int i = 1; i <= N; i++)
	{
		dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]);
		dp[i + 1] = max(dp[i], dp[i + 1]);
	}

	cout << dp[N + 1];
}

dp[i] : i번째날에 받을 수 있는 최대 금액

답은 N번째날까지 일하므로 dp[N+1]을 구합니다.

 

아래 코드는 i번째날 T[i]날이 걸리는 일을한다면 i+T[i]날에 받게될 최대 금액인데

일을 한다는 기준이다. 

dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]);

 

아래 코드는 일을 안하는 경우인데

i번째날 일을 안하다면 i+1번째날 dp[i] 돈이나 dp[i+1]이 모여져있을것이다.

dp[i + 1] = max(dp[i], dp[i + 1]);