1770. Maximum Score from Performing Multiplication Operations

문제: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/

Maximum Score from Performing Multiplication Operations - LeetCode

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

 left와 right로 연속되는 값들을 multipliers와 곱해서 가장 큰 스코어가 나오는 값을 구한다.   leftMost와 rightMost부터 출발하며 둘 중 하나를 선택하여 multipliers의 현재값과 곱해서 합한다.  multipliers의 길이만큼 더할 수 있다.  

 

 multipliers의 길이가 K라고 할 때, nums[0:K]를 먼저 구하고 K를 하나씩 decrement하면서 right의 값을 multipliers와 곱해서 total에 더하는 것을 생각할 수 있다.  K=5일 때, nums[0:K]는 예제에서 nums의 값 7까지 각각 곱하여 더한 상황이다.  이제 7을 빼고 right에서 하나 더해줘본다.  

 

 total += -(7 * 6) + (1 * 6)이 될 것이다.

 

 한 번 더 해주면,

 

 total += -(-2 * 4) + (7 * 6) - (1 * 6)이 된다.  이전에 더해줬던 (1 * 6)은 다시 빼줘야하므로 nums[0:K]에서 nums[len - k: len]까지 순차적으로 밀면서 total의 최댓값을 구하는게 불가능하다.

 

class Solution {
public:
    int cache[1001][1001];
    
    int traverse(vector<int>& nums, vector<int>& multipliers, int left, int right, int pos){
        if(pos == multipliers.size()){
            return 0;
        }
        
        int &ret = cache[left][right];
        if(ret != -1){
            return ret;
        }
        
        int leftV = nums[left] * multipliers[pos] + traverse(nums, multipliers, left + 1, right, pos + 1);
        
        int rightMost = nums.size() - 1 - (multipliers.size() - 1 - right);
        int rightV = nums[rightMost] * multipliers[pos] + traverse(nums, multipliers, left, right - 1, pos + 1);
        ret = max(leftV, rightV); 
        return ret;
    }
    
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        memset(cache, -1, sizeof(cache));
        return traverse(nums, multipliers, 0, multipliers.size() - 1, 0);
    }
};

 이에 위의 코드에서는 모든 경우의 수를 탐색하는 코드를 작성하였다.  주의할 점은 nums의 길이가 10^5이며, 왼쪽과 오른쪽에서 줄어드는 값을 nums의 길이로 캐싱하는 경우 10^10의 메모리를 요구하므로 할당이 불가함을 알 수 있다.

 

 cache를 사용하는 경우, 습관적으로 -1로 초기화를 시켰는데 흠 이게 유효한 값인지 좀 더 생각을...

 

 흠 memset을 -2로 하고 초기 진입인데 -16843010이 뜬다... 뭔가 이상하다.

 

 -1로 cache를 초기화하니 -1이 초기화된다.  버그인가...