[leetcode #877] Stone Game

Problem

Alex and Lee play a game with piles of stones. There are an even 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. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

**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.

Constraints:

・ 2 <= piles.length <= 500
・ piles.length is even.
・ 1 <= piles[i] <= 500
・ sum(piles) is odd.

Idea

Stone Game → Dynamic Programming이라고 봐도 무방하지 않을까 싶다. Stone Game은 돌무더기가 하나일 때부터 결과를 메모리에 저장하고, 돌무더기가 점점 늘어날 때 이전에 얻은 결과를 활용하면 된다. 이번 문제 또한 돌무더기의 개수가 작을 때 결과를 미리 저장해두고 나중에 활용하면서 풀었다.

https://velog.io/@timevoyage/LeetCode-1690-Stone-Game-VII
Stone Game VII에서는 두 플레이어의 점수 차이를 계산했지만 이번에는 Alex가 항상 게임에 이기는지 여부만 리턴하면 된다. 두 플레이어 모두 optimal한 선택을 한다고 가정한 후 두 플레이어의 점수를 나눠서 저장한 후 마지막에 Alex의 점수가 더 높은지 확인했다.

가장 앞쪽의 돌무더기가 i번째, 마지막 돌무더기가 j번째라고 가정하면 dp 공식은 다음과 같이 만들 수 있다.

alex[j] = Math.max(piles[i] + lee[j], piles[j] + lee[j-1])
lee[j] = if (alex choose i) alex[j] else alex[j-1]

어차피 lee도 매번 최선의 선택을 하기 때문에 alex는 앞쪽 또는 뒤쪽의 돌무더기를 선택한 후 lee가 선택한 값을 더하면 된다. lee는 Alex가 이전에 한 최선의 선택을 따르기만 하면 된다.

알고리즘을 여기까지 설계했다면 낚였다는 것을 눈치챌 수 있을 것이다. lee는 어차피 alex가 한 최선의 선택을 따르므로 alex의 돌무더기 개수보다 작을 수밖에 없다. return true;만 하면 끝나는 문제였던 것이다...! 어쩐지 이상하더라니...

Solution

class Solution {
  public boolean stoneGame(int[] piles) {
      int n = piles.length;
      int[] alex = new int[n];
      int[] lee = new int[n];
      int firstAlex = 0;
      int lastAlex = 0;

      for (int i=n-2; i >= 0; i--) {
          for (int j=i+1; j < n; j++) {
              firstAlex = piles[i] + lee[j];
              lastAlex = piles[j] + lee[j-1];
              if (firstAlex > lastAlex) {
                  lee[j] = alex[j] == 0 ? piles[j] : alex[j];
                  alex[j] = firstAlex;
              } else {
                  lee[j] = alex[j-1] == 0 ? piles[j-1] : alex[j-1];
                  alex[j] = lastAlex;
              }
          }
      }    
      return alex[n-1] > lee[n-1];
  }
}

더 간단하게 문제를 푸는 법은 다음과 같다.

class Solution {
    public boolean stoneGame(int[] piles) {
      return true;
  }
}

Reference

https://leetcode.com/problems/stone-game/