leetcode hard : Burst Balloons

https://leetcode.com/problems/burst-balloons/

Burst Balloons - LeetCode

 

이거 전체탐색 + memoization해서 top down dp로 풀면 생각보다 쉽게 풀릴수도..?

 

일단 Brute force [TLE]

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        def search(lst, coinsum):
            if len(lst) == 1:
                coinsum += lst[0]
                return coinsum

            max_coinsum = coinsum
            for i in range(len(lst)):
                left = 1 if i == 0 else lst[i - 1]
                right = 1 if i == len(lst) - 1 else lst[i + 1]
                newcoin = left * lst[i] * right

                max_coinsum = max(max_coinsum, search(lst[:i] + lst[i+1:], coinsum + newcoin))
            
            return max_coinsum
        
        return search(nums, 0)

정확성을 테스트하기 위해 submit해본다. 

Time Limit Exceeded가 뜨면 효율성은 구린데 정확성은 좋은거.

 

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        def search(lst):
            if len(lst) == 1:
                return lst[0]

            if lst in memo:
                return memo[lst]

            max_coinsum = 0
            for i in range(len(lst)):
                left = 1 if i == 0 else lst[i - 1]
                right = 1 if i == len(lst) - 1 else lst[i + 1]

                coinsum = left * lst[i] * right
                new_lst = lst[:i] + lst[i+1:]
                max_coinsum = max(max_coinsum, search(new_lst) + coinsum)
            
            memo[lst] = max_coinsum
            return max_coinsum

        memo = {}
        
        return search(tuple(nums))

그래도 TLE가 나네? ([8,3,4,3,5,0,5,6,6,2,8,5,6,2,3,8,3,5,1,0,2])

왜지..? ㅠㅠ

 

https://leetcode.com/problems/burst-balloons/solutions/892552/for-those-who-are-not-able-to-understand-any-solution-with-diagram/?orderBy=most_votes 

For those who are not able to understand any solution [WITH DIAGRAM] - Burst Balloons - LeetCode

func(lst , i, j) 형식으로 문제를 정의하는데

만약 k번째 balloon을 먼저 터뜨리고

func(lst, i, k-1), func(lst, k+1, j)를 sub problem으로 나누게 되면

터진 k번째 balloon때문에 두 subproblem은 independent하지 않게된다. (끝 풍선이 인접해있으므로)

그래서 k번째 balloon을 '마지막에' 터뜨리는걸로 한다.

 

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # dummy balloon 삽입 
        nums.append(1)
        nums.insert(0, 1)

        memo = [[-1] * 501 for _ in range(501)]

        def solve(i, j):
            if i > j: return 0
            if i == j: return nums[i - 1] * nums[i] * nums[i + 1]
            if memo[i][j] != -1: return memo[i][j]

            result = 0

            for k in range(i, j + 1):
                last = nums[k]

                # 경계값 i,j 옆에있는 애들을 곱한다. 양옆 다 터지고 나면 걔네만 남을거니까
                last *= nums[j + 1]
                last *= nums[i - 1]

                # 양옆을 터뜨리고 더한다.
                last += solve(i, k - 1) + solve(k + 1, j)
                
                result = max(result, last)

            memo[i][j] = result
            return result
        
        return solve(1, len(nums) - 2)

 

같은 코드 C++로 하면 통과하는데 파이썬이라 71/73 passed로 TLE 떴다. 파이썬 억까다!