[BOJ/C++] 14501 퇴사 : DP

문제

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

풀이

주식 문제랑 비슷하다고 생각해서 뒤에서부터 접근해야겠다고 생각은 했는데 DP 문제는 역시 생각하기가 까다롭다😭

뒤에서부터 접근하는데
if t[i]일 동안 상담하는데 그게 N보다 크면 dp[i]를 전에 계산한 dp[i+1]의 값으로 넣어줌
else dp[i] = max(dp[i+1], p[i] + dp[i+t[i]])

ex) p[2] = 5면 dp[2] = max(dp[3], p[2]+dp[7])

⚠️ if 경우에 처음에는 그냥 continue했는데 dp값을 계속 갱신하는 형태라 저렇게 값을 저장해줘야 정답 처리가 됨

코드

#include <iostream>
#include <algorithm>

using namespace std;

int t[16];
int p[16];
int dp[16];

int main() {
	int N;
	
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> t[i] >> p[i];

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

	cout << dp[1];

	return 0;
}