Daily LeetCode Challenge - 2140. Solving Questions With Brainpower

Problem From.

https://leetcode.com/problems/solving-questions-with-brainpower/

오늘 문제는 [점수, 파워] 로 주어진 배열이 있을때, 각각의 문제를 풀면서 얻을 수 있는 포인트의 최대를 구하는 문제였다. 문제 배열을 순회할때, 한 문제를 풀면 그 파워만큼의 문제를 건너뛰어야하는 제약 조건이 있었다.

이 문제는 DP 로 풀 수 있었는데, 문제의 끝에서부터 거꾸로 진행하면 되었다.
Example 1 로 보면, [2,5] 에서는 문제를 풀면 2 점 스킵하면 0 점을 얻으므로 2점을 dp[3] 에 넣어둔다.
[4,4] 에서는 문제를 풀면 4점 스킵하면, 그 전의 점수인 2 점이 최대이므로 4점을 얻는 쪽을 택하고 dp[2] 에 4를 넣어둔다.
[4,3] 에서는 문제를 풀면 4점 스킵하면, 그 전의 점수인 4점이 최대이므로 4점을 dp[1] 에 넣어둔다
[3,2] 에서는 문제를 풀면 3점 에다가 2개 건너뛴 곳 (dp[3]) 의 값은 2를 더한 5 를 얻을 수 있고, 스킵하면 그 전의 최대값 dp[1] 인 4를 얻을 수 있으므로, dp[0] 에 5를 저장한다.
마지막에 dp[0]의 값을 반환하면 최대값을 구할 수 있다.

class Solution {
    fun mostPoints(questions: Array<IntArray>): Long {
        var answerList = LongArray(questions.size + 1) { 0L }
        for(i in questions.size - 1 downTo 0) {
            val point = questions[i][0]
            val jump = questions[i][1]
            
            val index = Math.min(i + jump + 1, questions.size)
            val currentPoint = point + answerList[index]
            answerList[i] = Math.max(currentPoint, answerList[i+1])
            
        }
        return answerList[0]
    }
}