LeetCode_1140.Stone Game II

leetcode.com/problems/stone-game-ii/

Stone Game II - LeetCode

Solution1. 

class Solution:
    def stoneGameII(self, a: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(idx, M, isAlex):
            if idx > len(piles) : return 0
            
            if isAlex:
            	# Alice`s Turn : Alice가 가장 이득을 보는 선택 1~2M개의 돌무더기를 선택
                return max([sum(piles[idx:idx+x]) + minimax(idx+x, max(M,x),False) for x in range(1, 2*M + 1)])
            else:
            	# Bob`s Turn : Alice의 이득이 최소가 되느 1~2M개의 돌무더기를 선택
                return min([minimax(idx+x, max(M,x), True) for x in range(1, 2*M+1)])
        
        return minimax(0,1,True)

 

 

Solution 2.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
                
        n = len(piles)
        
        @lru_cache(None)
        def minimax(start_idx, M):
            if n - start_idx <= 2 * M:
            	# 남은 돌을 모두 가져갈수 있다면
                return sum(piles[start_idx:])
        
            max_score = 0
            all_sum = sum(piles[start_idx:])
            
            for X in range(1, 2 * M + 1):
            	# Bob이 최소 이득을 보는 경우를 선택 -> maximize(all_sum - bob`s profit)
                score = all_sum - minimax(start_idx + X, max(M, X))
                max_score = max(max_score, score)

            return max_score
        
        return minimax(0, 1)

 

 

Solution 2-1. suffix_sum을 통해 구간합을 구하지 않도록 개선

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        # suffix_sum
        n = len(piles)
        suffix_sum = [0 for _ in range(n)]
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = (suffix_sum[i + 1] if i + 1 < n else 0) + piles[i]
        
        @lru_cache(None)
        def minimax(start_idx, M):
            if n - start_idx <= 2 * M:
                return suffix_sum[start_idx] # sum(piles[start_idx:])
                
            max_score = 0
            all_sum = suffix_sum[start_idx] # sum(piles[start_idx:])
            
            for X in range(1, 2 * M + 1):
                score = all_sum - minimax(start_idx + X, max(M, X))
                max_score = max(max_score, score)

            return max_score
        
        return minimax(0, 1)

 

 

※ suffix_sum array : 끝에서부터 배열을 누적 시키거나, 배열의 누적합을 뒤집어서 생성. 특정 idx부터 배열 끝까지의 합을 바로바로 사용할수 있음

nums = [1,2,3,4,5]

n = len(nums)
suffix_sum = [0 for _ in range(n)] 
# [0,0,0,0,0]

for i in range(n - 1, -1, -1):
	suffix_sum[i] = (suffix_sum[i + 1] if i + 1 < n else 0) + piles[i]

# suffix_sum = [15,14,12,9,5]
# suffix_sum[0] -> 배열의 0 번째부터 배열 끝까지의 합, 1+2+3+4+5=15
# suffix_sum[3] -> 배열의 3 번째부터 배열 끝까지의 합, 4+5=9