leetcode 877 - Stone Game

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

풀이

현재 플레이어가 할 수 있는 액션은 왼쪽 pile을 가져가거나 오른쪽 pile을 가져가거나 둘 중 하나다. 따라서 두 가지 경우 중 더 유리한 경우를 선택하면 된다. 재귀적으로 하나씩 계속 가져갔을 때 가장 마지막 상태, 즉 pile이 한 개 남은 상태라면 승패는 명확하다. 선공을 통해 먼저 가져가면 이긴다.

 

그러면 이제 반대로 맨 마지막 기저 조건과 점화식을 통해 식을 세울 수 있다. 점화식을 세울 때 단순히 이기고 지는 정보만 저장하면 안 되고, 서로 최선을 다했을 때 얼마나 차이가 나는지 까지 저장을 해야 한다. 

d[i][j] = i부터 j까지 pile로 게임을 진행할 때 선공을 한 사람이 가져갈 수 있는 최대 이득

 

아래 코드에서는 pile이 한 개 있을 때를 기저 조건으로 먼저 구해놓고, 두 개 이상인 경우에 대해서 점화식을 통해 구했다.

 

코드

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> d(n, vector<int>(n));
        
        for(int i = 0; i < n; i++) d[i][i] = piles[i];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < n-i; j++) {
                d[j][j+i] = max(piles[j] - d[j+1][j+i], piles[j+i] - d[j][j+i-1]);
            }
        }
        
        return d[0][n-1] > 0;
    }
};