[LeetCode] 2140. Solving Questions With Brainpower

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

Solving Questions With Brainpower - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

You are given a 0-indexed 2D integer array questions where questions[i] = [points(i), brainpower(i)].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
  • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

 

[points, brainpower]를 요소로 가지는 2차원 배열 questions가 있다.

문제를 풀거나 풀지 않을 수 있는데, 문제를 풀면 points를 얻고, brainpower만큼 다음 문제를 풀 수 없다.

또는 문제를 풀지 않고 다음 문제로 넘어갈 수 있다.

최대로 벌 수 있는 점수를 구하시오.

 

 

풀이

맨 뒤 인덱스부터 시작한다.

i번째부터 시작했을 경우의 값을 구하고, 그 앞에 값과 비교하여 더 큰 값을 dp테이블에 저장한다.

계속 반복해서 0번째 인덱스에는 최선의 포인트가 남는다.

 

코드(C++)

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> dp (n+1);

        for(int i = n-1; i >= 0; i--){
            int points = questions[i][0];
            int brainpower = questions[i][1];
            int next_idx = i + brainpower + 1;
            long long next_points = next_idx < n? dp[next_idx] : 0;
            dp[i] = max(next_points + points, dp[i+1]);
        }
        return dp[0];
    }
};