[BOJ] 14501

[HyomK]

백준 14501 퇴사
https://www.acmicpc.net/problem/14501
[문제유형] 다이나믹 프로그래밍 , 브루트포스 알고리즘

점화식

if (i + t[i] <= n) dp[i] = max(dp[i + time[i]], dp[i + time[i]] + pay[i])

현재 날짜에서 소요 시간과 비용을 더해 dp에 저장한다.
dp : N일에 얻을 수 있는 최대 수익이후, 중복될 때 최대값을 넣는다.

 val dp = IntArray(N+1){0}

for(i in 0 until N){
            val next = i+time[i]
            //날짜가 범위를 넘어가지 않는 경우
            if(next<=N) {
                dp[next] = Math.max(dp[next] , dp[i]+pay[i])
            }
            dp[i+1] = Math.max(dp[i+1],dp[i]) 
        }

next는 x번째 날 일을 했을 때 끝나서 다시 시작할 수 있는 당일을 의미한다

ex) 1번째날의 업무가 3일 걸린다면 1,2,3 일까지 일하고 4일부터 새로운 일을 시작할 수 있을 것이다.