1937. Maximum Number of Points with Cost

https://leetcode.com/problems/maximum-number-of-points-with-cost/description/?envType=daily-question&envId=2024-08-17

 

leetcode - Maximum Number of Points with Cost

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

문제 난이도 : Medium

 

문제

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

• x for x >= 0.
• -x for x < 0.

m x n의 정수 행렬 points가 있다.

0점부터 시작해서, 행렬로부터 최대 점수를 얻으려고 한다.

점수를 얻기 위해서, 각 열별로 하나씩 셀을 골라야 한다.

(r, c)에 도달하면, pointc[r][c]를 얻는다.

그러나, 다음 행에서 이동하는 열의 거리만큼 점수 감점이 적용된다.

거리는 각 열끼리의 차이다.

 

얻을 수 있는 최대 점수를 구하시오.

 

풀이

우선, 두 개의 배열을 준비한다.

하나는 prev, 하나는 curr로, 이전 열과 현재 열을 저장한다.

처음에, prev는 points의 0행 값들로 한다.

 

그리고, 1행을 순회하면서부터, 다음을 수행한다:

 left배열을 만들어서 left[j] = 이전 행에서 왼쪽으로부터 j열까지 가져온 값들 중 최고 값을 저장한다.

 right배열을 만들어서 right[j] = 이전 행에서 왼쪽으로부터 j열까지 가져온 값들 중 최고 값을 저장한다.

 그리고, curr[j]에 left[j]와 right[j]중 최고의 값을 구해서 이번에 얻는 수인 points[i][j]와 더한다.

 그리고, prev에 curr을 그대로 옮긴다.

 

위 과정이 끝나고, prev, curr둘다 각 열을 목적지로 했을 때 최고의 값이 남아있는데, 배열 중에서 최대값을 반환하면 된다.

 

코드

C++

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int m = points.size();
        int n = points[0].size();
        vector<long long> prev(n, 0), curr(n, 0);

        for (int j = 0; j < n; ++j) {
            prev[j] = points[0][j];
        }

        for (int i = 1; i < m; ++i) {
            vector<long long> left(n, 0);
            left[0] = prev[0];
            for (int j = 1; j < n; ++j) {
                left[j] = max(left[j-1] - 1, prev[j]);
            }

            vector<long long> right(n, 0);
            right[n-1] = prev[n-1];
            for (int j = n-2; j >= 0; --j) {
                right[j] = max(right[j+1] - 1, prev[j]);
            }

            for (int j = 0; j < n; ++j) {
                curr[j] = points[i][j] + max(left[j], right[j]);
            }
            prev = curr;
        }
        return *max_element(prev.begin(), prev.end());
    }
};