[LeetCode] 877. Stone Game

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

 

문제

알렉스와 리는 돌 더미로 게임을 한다. 한 줄에 짝수개의 돌 더미가 배열되어 있고, 각 더미 piles[i]는 양의 정수 개의 돌이 있다.

 

게임의 목적은 마지막에 가장 많은 돌을 갖는 것이다. 돌의 전체 개수는 홀수개라서 동점은 있을 수 없다.

 

알렉스와 리는 자기 차례에만 플레이를 하며, 알렉스의 차례로 게임이 시작된다. 각 차례에 플레이어는 줄의 시작 또는 끝에서 전체 돌 더미를 가져온다. 더 이상 남은 더미가 없을 때까지 지속되며, 가장 많은 돌을 가진 사람이 승자가 된다.

 

알렉스와 리는 최적의 플레이를 수행한다고 가정하고, 알렉스가 게임에서 이길수 있다면 True를 반환하라.

 

예제

Input: piles = [5,3,4,5]
Output: true

Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

 

풀이

게임 플레이 규칙에 따라, 한 플레이어는 자신의 차례에 두가지 선택 사항이 존재한다. 만약 dp[i][j]가 piles의 i ~ j 에서 얻을 수 있는 최고의 점수를 저장하고 있는 배열이라 가정한다면, 다음과 같이 선택에 따라 얻을 수 있는 점수를 예측할 수 있다.

• 플레이어가 첫 돌 더미를 선택한다면,
  • takeStart = sum - dp[i+1][j]
  • sum = i ~ j 범위의 돌 더미(piles)의 합
• 플레이어가 마지막 돌 더미를 선택한다면,
  • takeEnd = sum - dp[i][j-1]
  • sum = i ~ j 범위의 돌 더미(piles)의 합
• 최종적으로 두 선택 중에서 더 큰 점수를 얻을 수 있는 선택을 하면 된다.

 

이러한 관계를 코드로 작성하면 다음과 같다.

const N = piles.length;
const dp = new Array(N).fill(0).map(val => new Array(N).fill(0));

var play = function(piles, i, j) {
  if (i == j) {
  	return piles[i];
  }

  if (dp[i][j]) { return dp[i][j]; }

  let sum = 0;
  for (let s = i; s <= j; s++) { sum += piles[s]; }

  const takeLeft = sum - (dp[i+1][j] ? dp[i+1][j] : play(piles, i+1, j));
  const takeRight = sum - (dp[i][j-1] ? dp[i][j-1] : play(piles, i, j-1));

  dp[i][j] = Math.max(takeLeft, takeRight);

  return dp[i][j];
}

이러한 play 함수를 piles의 전체 범위에 대해서 수행하게 되면, dp[0][N-1]에는 게임 시작 플레이어가 얻을 수 있는 최고의 점수가 기록된다.

 

이 플레이어가 이겼는지 확인하기 위해서 돌의 총 개수 중 절반 이상을 해당 플레이어가 얻게 되는지 확인하면 된다.

const totalStone = piles.reduce((a, b) => a + b);

let reuslt = dp[0][N-1] > totalSocre/2;

최종 코드는 아래와 같다.

var stoneGame = function(piles) {
    const N = piles.length;
    const dp = new Array(N).fill(0).map(val => new Array(N).fill(0));
    
    var play = function(piles, i, j) {
        if (i == j) {
            return piles[i];
        }
        
        if (dp[i][j]) { return dp[i][j]; }
        
        let sum = 0;
        for (let s = i; s <= j; s++) { sum += piles[s]; }
        
        const takeLeft = sum - (dp[i+1][j] ? dp[i+1][j] : play(piles, i+1, j));
        const takeRight = sum - (dp[i][j-1] ? dp[i][j-1] : play(piles, i, j-1));
        
        dp[i][j] = Math.max(takeLeft, takeRight);
        
        return dp[i][j];
    }
    
    const totalStone = piles.reduce((a, b) => a + b);
    
    play(piles, 0, N-1);
    
    return dp[0][N-1] > (totalStone/2);
};

 

Github: 877.js

GitHub - opwe37/Algorithm-Study