[LeetCode] 1140. Stone Game II

문제 출처: https://leetcode.com/problems/stone-game-ii/

Stone Game II - LeetCode

 

문제

Alice와 Bob이 돌 더미를 가지고 게임을 한다. 여러 돌 더미들이 한 줄로 배열되어 있으며, 각 더미 piles[i] 는 양의 정수 값을 갖는다. 게임의 목표는 최종적으로 가능한 많은 돌을 얻는 것이다.

 

Alice와 Bob은 돌아가며 플레이를 하고, Alice가 처음으로 시작한다. 초기 M = 1 이다.

 

각 플레이어는 자신의 차례에서 남아있는 더미 중 첫 X개 더미의 모든 돌을 갖는데, 1 <= X <= 2M 이다. 그런 다음, M = max(M, X) 로 설정한다.

 

게임은 더 이상 선택할 돌 더미가 없을 때까지 지속된다.

 

Alice와 Bob이 최적의 플레이를 한다고 가정할 때, Alice가 얻을 수 있는 돌의 최대 수를 반환하라.

 

예제

Input: piles = [2,7,9,4,4]
Output: 10

Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Input: piles = [1,2,3,4,5,100]
Output: 104

 

풀이

처음 문제를 보고, 최적의 플레이가 어떤 선택인지에 대해서 고민을 했지만 최적의 선택의 패턴을 찾기가 어려웠다.

 

그래서!! 최적의 플레이가 뭔지에 대한 고민을 접어두고, Alice(혹은 Bob)가 현재 상황에서 어떤 선택을 했을 때 다음 턴부터 Bob(혹은 Alice)가 (뭔지 모르겠지만) 최적의 플레이를 통해 얻는 최종 돌의 수를 알려주는 함수가 있다고 가정하였다.

 

그 함수의 이름이 calcGetMaxStone 이라 할 때, 아래의 코드처럼 Alice가 얻을 돌의 수를 구할 수 있다.

var stoneGameII = function(piles) {
    const sum = piles.reduce((acc, val) => acc + val));
    
    // 여기서 calcGetMaxStone에 전달하는 매개변수의 경우 임시 매개변수로,
    // Alice가 몇개의 돌 더미를 선택했는지 표시하기 위함
    const selectOne = sum - calcGetMaxStone(1);
    const selectTwo = sum - calcGetMaxStone(2);
    
    return selectOne > selectTwo ? selectOne : selectTwo;
}

calcGetMaxStone 에 대해서 고민해보자.

 

calcGetMaxStone 는 위에서 언급한 것처럼 Alice(혹은 Bob)가 현 상황에서 어떤 선택(몇 개의 돌 더미를 가져올 것인가)을 한 후, 상대방이 가질 수 있는 최대의 돌이 몇 개인지를 반환해 주어야 한다.

 

이제 구현에 대해 고민해봐야 하는데, 이전에 언급했던 것처럼 최적의 플레이에 대한 패턴은 모르겠다고 했으므로, calcGetMaxStone 을 다시 이용하여 재귀적으로 답을 구하려고 한다.

 

Alice가 처음 1개의 더미를 선택했다면, Bob 입장에서는 남아있는 돌 더미와 현재의 M에 따라서 선택을 할 것이고, 그 선택에 대해서 본인이 얻을 수 있는 최대의 돌 수를 알기 위해서는 다시, Alice가 이후, 플레이에 영향을 받을 것이다. 이를 calcGetMaxStone 의 호출로 정리로 정리를 하면 아래와 같다. 누구의 값을 계산하는 건지 명확히 하기 위해서 이름(선택한 더미의 수)_calcGetMaxStone 형식으로 표현하였다.

piles = [2,7,9,4,4], M = 1

Alice(1)_calcGetMaxStone: remainPile = [7, 9, 4, 4], M = 1
	=> Bob(1)_calcGetMaxStone: remainPile = [9, 4, 4], M = 1
		=> Alice(1)_calcGetMaxStone: remainPile = [4, 4], M = 1
			=> Bob(1)_calcGetMaxStone: remainPile = [4], M = 1
				=> Alice(1)_calcGetMaxStone: remainPile = [], M = 1
			=> Bob(2)_calcGetMaxStone: remainPile = [], M = 2
        
		=> Alice(2)_calcGetMaxStone: remainPile = [4], M = 2
			=> Bob(1)_calcGetMaxStone: remainPile = [], M = 2
   
	=> Bob(2)_calcGetMaxStone: remainPile = [4, 4], M = 2
		=> Alice(1)_calcGetMaxStone: remainPile = [4], M = 2
			=> Bob(1)_calcGetMaxStone: remainPile = [], M = 2
            
		=> Alice(2)_calcGetMaxStone: remainPile = [], M = 2

위 내용을 그대로 코드로 작성해보면 아래와 같다.

var calcGetMaxStone = function(remainPiles, m) {
    if (remainPiles.length == 0) { return 0; }
    
    const sum = remainPiles.reduce((acc, val) => acc + val);
    if (remainPiles.length <= 2*m) { return sum; }
    
    let res = -Infinity;
    for (let i = 1; i < 2*m; i++) {
    	const remain = remainPiles.slice(i);
        const nextM = Math.max(m, i);
        res = Math.max(res, sum - calcGetMaxStone(remain, nextM));
    }
    return res;
}

이렇게 구현한 calcGetMaxStone 을 이용하여 메인 함수를 수정하면 아래와 같다. 단순히 calcGetMaxStone 를 호출하기만 하면 된다.

var stoneGameII = function(piles) {
    return calcGetMaxStone(piles, 1);
}

이 코드를 제출하면 안타깝게도 시간초과(Time Limit Exceeded) 를 만나게 된다. 이 문제를 해결하기 위해서 DP(Dynamic Programming)을 적용할 수 있다.

 

아래 코드의 경우, 남아 있는 돌 중 맨 앞에 있는 돌이 원래 몇 번째 돌인지에 대한 정보와 m 의 정보를 키 값으로 활용하고, 그때 얻는 결과를 저장하도록 하여 문제를 해결한 코드이다.

var stoneGameII = function(piles) {
    const dp = new Map();
    
    function calcGetMaxStones (piles, m, k) {
        if (piles.length == 0) { return 0; }
        
        const sum = piles.reduce((acc, val) => acc + val);
        if (piles.length <= 2*m) { return sum; }
        
        const dpKey = k.toString() + m.toString();
        if (dp.has(dpKey)) {
            return dp.get(dpKey);
        }
                
        let maxStone = -Infinity;
        for (let i = 1; i <= 2*m; i++) {
            const tmpMaxStone = sum - calcGetMaxStones(piles.slice(i), Math.max(i, m), k+i);
            maxStone = Math.max(maxStone, tmpMaxStone);
        }
        
        dp.set(dpKey, maxStone);
        
        return maxStone;
    }
    
    return calcGetMaxStones(piles, 1, 0);
};

 

 

Github: 1140.js

GitHub - opwe37/Algorithm-Study