백준 15486 퇴사 2

백준 15486
퇴사 1에서는 n이 크지 않아 재귀로 풀어도 됐지만 n이 최대 백오십만개이기 때문에 dp도 함께 이용해야 한다. 재귀로 풀려면 dp로 메모이제이션 사용해서 풀수도 있다.

bottom-up 방식에서 dp[i]는 i번째 날까지의 최대 이익이다.
첫 번째 날부터 일을 했을 때 얻을 수 있는 최대 이익을 계속 구한다.

Top-bottom 방식에서는 dp[i]는 i번째 날 일했을 때 얻을 수 있는 최대이익이다.
n 번째 날을 기점으로 그 날 일을 했을 때와 일을 안했을 때를 비교하면 된다.
i번째 날 일을 했을 때는 그 날부터 일을 했을 때의 이익과 그 일이 끝나는 다음 날의 dp 값을 더해주면 된다 => dp[i]=profit+dp[i+day]
i번째 날 일을 안했을 때는 dp[i]=dp[i+1] 이다.

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>v;
int dp[15000001];
int n;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	/*
	for (int i = 1; i <= n; i++) { // => bottom-Up 방법 dp[i]의 의미 i날까지의 최대 이익
		int day = v[i - 1].first;
		int profit = v[i - 1].second;

		dp[i] = max(dp[i],dp[i - 1]);
		if (i + day > n + 1) continue;
		dp[i + day-1] = max(dp[i + day-1], profit+dp[i-1]);
	}
	*/

		for (int i = n; i >= 1; i--) { // => Top-bottom 방법 dp[i]의 의미 i날 일했을 때 얻을 수 있는 최대 이익
		int day = v[i - 1].first; 
		int profit = v[i - 1].second;

		if (i + day > n + 1) dp[i] = dp[i + 1];
		else dp[i] = max(dp[i + 1], profit + dp[i + day]);

	}
	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
	cout << ans;
}