leetcode : Maximum Score from Performing Multiplication Operations

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

Maximum Score from Performing Multiplication Operations - LeetCode

 

그리디 문제인가 싶지만 잘 생각해보면 greedy하게 답을 구하면 optimal이 아닐 수도 있다. 매 순간마다 left를 택하냐 right를 택하냐의 선택지가 주어지는 search문제기 때문에 naively O(2^N) 알고리즘으로 bruteforce를 할 수 있고 DP를 쉽게 연상할 수 있다.

 

근데 구현은 답 안보곤 못하겠더라.

 

일단 Bruteforce

class Solution:
    def maximumScore(self, nums: List[int], mults: List[int]) -> int:
        def search(l, i):
            if i == len(mults):
                return 0
            
            r = len(nums) - 1 - (i - l)
            ifWeChooseLeft = mults[i] * nums[l] + search(l + 1 , i + 1)
            ifWeChooseRight = mults[i] * nums[r] + search(l, i + 1)
            return max(ifWeChooseLeft, ifWeChooseRight)
        
        return search(0, 0)

 

l은 왼쪽으로부터 l개 썼다 이런 의미고 i는 곱셈을 i번 수행했다 이런의미다.

search(l, i)는 상태 l,i로부터 탐색해서 최대값을 구하겠다 그러니까 왼쪽에서 l개 오른쪽에서 i-l개를 이미 쓴 상태에서 나머지 가지고 최대값을 구한다는 의미다.

 

여기서 memoization만 살짝 적용해주자

class Solution:
    def maximumScore(self, nums: List[int], mults: List[int]) -> int:
        dp = [[0] * 1001 for _ in range(1001)]
        
        def search(l, i): 
            if i == len(mults):
                return 0
            
            if dp[l][i]:
                return dp[l][i]
            
            r = len(nums) - 1 - (i - l)
            ifWeChooseLeft = mults[i] * nums[l] + search(l + 1 , i + 1)
            ifWeChooseRight = mults[i] * nums[r] + search(l, i + 1)
            dp[l][i] = max(ifWeChooseLeft, ifWeChooseRight)
            return dp[l][i]
        
        return search(0, 0)

 

근데 이 문제는 discussion을 보니까 Python으로 풀면 거의 TLE가 뜨는 듯 하다.

bottom up dp로 바꿔줄 필요가 있다.

 

재귀의 종료조건까지 가서 생각해보면 search( ?? , len(mults) ) 부터 계산되어 있어야 bottom up dp로 차근차근 search(l + 1 , i + 1), search(l, i + 1) 이것들을 이용해서 max값을 구해가는게 가능하다.

 

class Solution:
    def maximumScore(self, nums: List[int], mults: List[int]) -> int:
        dp = [[0] * (len(mults)+1) for _ in range(len(mults)+1)]
        
        for i in range(len(mults) - 1, -1, -1):
            for l in range(len(mults) - 1, -1, -1):
                if i < l:
                    continue
                
                r = len(nums) - 1 - (i - l)
                
                ifWeChooseLeft = mults[i] * nums[l] + dp[l+1][i+1]
                ifWeChooseRight = mults[i] * nums[r] + dp[l][i+1]
                dp[l][i] = max(ifWeChooseLeft, ifWeChooseRight)
        
        return dp[0][0]

 

굵은글씨 친 부분은 bottom up dp를 하면서 생기는 이상한 상황을 방지해주는건데 i(곱셈 수행횟수)보다 l(왼쪽 곱셈횟수)가 많은게 말이 안된다. 이럴 경우에는 index out이 뜨니 필히 방지해줘야됨.

그래도 TLE나네.. 파이썬으론 못푸는 문젠가보다.

 

Java로 컨버팅해보자.

class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int[][] dp = new int[1001][1001];
        
        for(int i = multipliers.length - 1; i >= 0; i-- ){
            for(int l = multipliers.length - 1; l >= 0; l--){
                if (i < l) continue;
                int r = nums.length - 1 - (i - l);
                int chooseLeft = multipliers[i] * nums[l] + dp[l+1][i+1];
                int chooseRight = multipliers[i] * nums[r] + dp[l][i+1];
                dp[l][i] = Math.max(chooseLeft, chooseRight);
            }
        }
        
        return dp[0][0];
    }
}

텅과~!