[LeetCode] 2140. Solving Questions With Brainpower (Python)

 

 

난이도: Medium

Problem Description

---

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

 

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.

 

 

Problem Example

---

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

 

Constraints

---

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

 

 

✏️ Solution

---

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * (n+1)

        for i in range(n-1, -1, -1):
            point, brain_power = questions[i]
            next_idx = i + brain_power + 1

            if next_idx < n:
                dp[i] = dp[next_idx] + point
            else:
                dp[i] = point
            
            dp[i] = max(dp[i], dp[i+1])

        return dp[0]

오랜만에 코딩 문제를 푼 것 같다.

 

이 문제는 classic한 dp 문제였다.

 

각 문제를 skip하거나 풀면서 획득할 수 있는 최대 점수를 반환하면 됐다.

 

먼저 questions의 뒤 문제부터 확인하면서 최대 점수를 구해나갔다.

 

그러다가 함께 풀 수 있는 문제가 나오면 현재 점수와 지금까지의 최대 점수와 더해서 최대 점수를 업데이트 했다.

 

마지막에는 dp[0]을 반환하여 정답을 맞출 수 있었다.

 

⚙️ Runtime & Memory

---

 

 

---

문제: 2140. Solving Questions With Brainpower

 

깃허브: github

algorithmPractice/LeetCode/2262-solving-questions-with-brainpower at main · laewonJeong/algorithmPractice