728x90
풀이
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값을 뒤에서 부터 넣어주는 경우도 배워간다 ㅜ ㅜ
어렵다
728x90
'CS > Algorithm' 카테고리의 다른 글
[ JAVA / 백준 : 1699 ] 제곱수의 합 (0) | 2021.08.22 |
---|---|
[ JAVA / 백준 : 2193 ] 이친수 (0) | 2021.08.22 |
[ JAVA / 백준 : 9461 ] 파도반 수열 (0) | 2021.08.22 |
[ JAVA / 백준 : 1904 ] 01타일 (0) | 2021.08.22 |
[ JAVA / 백준 : 9095] 1, 2, 3 더하기 (0) | 2021.08.20 |