[ JAVA / 백준 : 14501 ] 퇴사

풀이

for(int i = N; i > 0; i--) {
	int day = i + date[i];
			
	if(day > N + 1)
		dp[i] = dp[i + 1];
	else
		dp[i] = Math.max(dp[i + 1], pay[i] + dp[day]);
}

가장 중요한 조건! 뒤에서부터 계산을 해준다. 

N일차부터 1일차까지 계산

N일차일 경우에 일할 수 있는 날짜 계산. date[N] 이 1이면 일할 수 있고 아니면 일할 수 없음. 

일할 수 있는 경우, (이번 일해서 받는 pay + dp[day] : 이번 일이 끝나고 받을 수 있는 pay)와 이번일을 안했을 경우의 값을 비교해준다 . dp[i] = Math.max(dp[i + 1], pay[i] + dp[day]);

 

 

뒤에서부터 계산을 차근차근해서, max값을 뒤에서 부터 넣어주는 경우도 배워간다 ㅜ ㅜ

어렵다