백준 14501번 퇴사(C++)

DP는 쉬워보이는데 막상 구현하면 꽤어렵다. 

이문제에서 헷갈렸던 부분은 다음 dp값을 갱신을 n+1날짜가 넘어걸때는 해주지말아야하는데(if(i+t1[i]>n+1)continue;)

현재 dp값을 갱신하는건 넘어가던지 상관없이 했어야하는데 이부분의 위치를 잘못설정해서 틀렸었습니다가 떴었다.

 

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


int main() {

	
	vector<int>dp; 
	int n;
	cin >> n;
	vector<int>t1; t1.assign(n+1, 0);
	vector<int>p1; p1.assign(n+1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> t1[i] >> p1[i]; 
	}
	dp.assign(n+2, 0);
	//최대 수익 출력하기 
	int m = 0; 
	for (int i = 1; i <= n; i++) {
		dp[i] = max(dp[i], m);
		m = max(dp[i], m); //이것도
		if (i + t1[i] > n+1)continue; //날짜 초과되면 저장 안함 -> 이것만 안하고 갱신은 해줘야함 
	   //과연 0일때만 바꿔야할까? 
		//이전까지 최댓값이 있으면 바꿔주기 
		//다음값 갱신
		dp[i + t1[i]] = max(dp[i + t1[i]],dp[i] + p1[i]);
		
	
	}
	m=max(m,dp[n+1]);
	cout <<m;

}