[LeetCode] 1140. Stone Game II

https://leetcode.com/problems/stone-game-ii/description/?envType=daily-question&envId=2024-08-20

leetcode - Stone Game II

문제 유형 : 다이나믹 프로그래밍, 부분합

문제 난이도 : Medium

 

문제

Alice and Bob continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

 

Alice와 Bob은 돌을 가져가는 게임을 하고 있다.

돌 조각들은 일렬로 나열되어있고, piles[i]를 순차적으로 모두 가져가야한다.

처음에, M=1로 시작한다.

각 플레이어의 차례에서, 첫 X개의 돌 조각들을 가져갈 수 있다. (1 <= X <= 2M)

그리고, M을 max(M, X)로 업데이트한다.

모든 돌을 챙길 때 까지 게임이 계속된다.

 

Alice가 최대한 챙길 수 있는 돌 조각의 최대 개수를 구하시오.

 

풀이

dp[idx][m]을 idx번부터 줍는다고 했을 때, M을 m으로 시작할 때의 Alice의 최대 돌조각 개수이다.

 

후위부 합을 담는 suffixSum 배열을 만들어서 후위부를 누적시킨다.

각 idx에 대해서 뒤부터 다음의 과정을 따른다:

각 m을 1부터 n까지 반복한다:

만약 i + 2 * m >= n이면, suffixSum 그대로 가져온다. 남은 돌을 모두 챙길 수 있다는 뜻이기 때문이다.

아니면, 1부터 2 * M 사이의 돌을 선택한다.

 이때, Alice가 챙길 수 있는 최대는 suffixSum[i] - dp[i+x][max(m, x)] (즉, 전체 후위부 부분합 - Bob이 가져갈 수 있는 수)이다.

이 둘 중에서 dp테이블에 저장한다.

 

최종적으로, Dp[0][1]을 반환한다.

 

 

코드

C++

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        
        vector<vector<int>> dp(n, vector<int>(n + 1, 0));
        vector<int> suffixSum(n, 0);
        suffixSum[n - 1] = piles[n - 1];
        
        for (int i = n - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        
        for (int i = n - 1; i >= 0; i--) {
            for (int m = 1; m <= n; m++) {
                if (i + 2 * m >= n) {
                    dp[i][m] = suffixSum[i];
                } else {
                    for (int x = 1; x <= 2 * m; x++) {
                        dp[i][m] = max(dp[i][m], suffixSum[i] - dp[i + x][max(m, x)]);
                    }
                }
            }
        }
        
        return dp[0][1];
    }
};