LeetCode - 2140. Solving Questions With Brainpower

문제링크

 

문제 설명

0-indexed 2차원 정수 배열 questions가 주어집니다.
각 questions[i] = [pointsi, brainpoweri]는 시험의 i번째 문제에 대한 정보를 나타냅니다.

• pointsi: i번 문제를 풀었을 때 얻는 점수
• brainpoweri: i번 문제를 풀 경우, 그 다음의 brainpoweri개 문제는 건너뛰어야 합니다.

문제는 순서대로 풀어야 하며, 각 문제에 대해 풀거나(solve) 건너뛸지(skip)를 결정해야 합니다.

예를 들어,
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]일 때:

• 0번 문제를 풀면 3점을 얻지만, 1번과 2번 문제는 건너뛰어야 합니다.
• 0번을 건너뛰고 1번을 풀면 4점을 얻지만, 2번과 3번 문제는 건너뛰어야 합니다.

시험에서 얻을 수 있는 최대 점수를 반환하세요.

제한 사항

• 1 <= questions.length <= 10^5
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 10^5

예시

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.

풀이 흐름

• 문제를 읽고서 바로 dp를 떠올렸습니다.
  • dp의 대표 문제 중 하나인 계단 오르기와 유사해서 그랬던 것 같습니다.
• 이전에는 바텀 업 방식을 자주 사용했지만 요즘은 탑 다운 방식을 연습하고 있습니다.
• 탑 다운에서 가장 중요한 것은 함수를 설정하는 것 입니다.
• 풀의에서 정의한 f라는 함수에 대한 정의를 저는 d 인덱스에서 시작했을 때 얻을 수 있는 점수의 최댓값을 구하는 함수라고 정의했습니다.
• 탈출 조건으로 d 인덱스가 questions의 범위 밖이면 0을 반환하도록 설정했습니다.
• 이제 현재 d 인덱스에서 얻을 수 있는 점수의 최댓값은
  1. 현재 문제를 건너뛰고 다음 문제부터 얻을 수 있는 점수의 최댓값
  2. 현재 문제를 풀고 brainpoweri 만큼 건너뛴 문제부터 얻을 수 있는 점수의 최댓값
• 위 2개 중 최댓값이 현재 d 인덱스에서 얻을 수 있는 점수의 최댓값입니다.

코드

import java.util.Arrays;

class Solution {
    long[] dp;
    public long mostPoints(int[][] questions) {
        dp = new long[questions.length];
        Arrays.fill(dp, -1);
        return f(0, questions);
    }

    private long f(int d, int[][] questions) {
        if (d >= questions.length) {
            return 0;
        }
        if (dp[d] != -1) return dp[d];
        dp[d] = Math.max(f(d + 1, questions), f(d + questions[d][1] + 1, questions) + questions[d][0]);
        return dp[d];
    }
}