Python으로 푸는 LeetCode 877. Stone Game

LeetCode 877. <Stone Game> 문제는 Dynamic Programming 에 관한 문제이다. 

문제를 푸는 방법에 대해서는 Solution에 자세히 나와있지만 포스팅 하며 알게 된 내용들을 정리하고 

나중에 다시 이 문제를 찾아볼 때 빠르게 이해할 수 있도록 이 글을 작성한다.

···

array에 숫자들이 들어있고, Alex와 Lee가 맨 앞과 맨 뒤 중에 원하는 위치의 숫자를 번갈아 가면서 뽑는다. 

Alex가 항상 먼저 뽑는다고 했을 때, Alex가 항상 이기는 경우 True를 반환하도록 한다.

LeetCode에서 문제보기

Dynamic Programming으로 풀기

Alex와 Lee가 게임을 마치려면 piles에서 숫자를 꺼내는 각각의 작은 작업들을 번갈아 수행해야하고, 이러한 반복 작업은 DP를 활용한 재귀로 구현할 수 있다.

 piles = [5, 3, 4, 5]이며 숫자를 뽑는 작업을 DP라고 정의한다.  Alex가 먼저 숫자를 뽑는다고 하였을 때, Alex는 노란색으로 칠해진 5(i=0)와 5(i=3) 중에 하나를 선택할 수 있다. 

i	0	1	2	3
v	5	3	4	5

Alex가 그 이후에 뽑게될 원소가 무엇인지는 모르겠지만, Alex가 뽑을 최대 값은 2가지 경우이다.

 1, 앞의 원소를 선택하고, 그 나머지 piles에서 다음 원소를 뽑을 경우와 2. 맨 뒤의 원소를 선택하고 그 나머지 piles에서 다음 원소를 뽑게 될 경우이다.

즉, max( 5(i=0) + DP( [3, 4, 5] ),   5(i=3) + DP( [5, 3, 4] ))이다.

이렇게 문제를 풀어보자

사실, 이 문제는 Alex의 승패가 중요할 뿐 Lee의 총 점수가 얼마일지는 중요하지 않다. 그래서 이렇게 문제를 바꿔서 풀어보자.

piles가 다 비워질때까지 Alex는 자신의 점수를 더해간다. Lee는 점수를 얻을 때마다 Alex의 총 점수에서 얻은 점수를 빼준다. 

최종 점수가 양수면 Alex가 이기는거고 음수면 Lee가 이긴다. (음수가 되었다는 건 Lee가 뽑은 숫자가 Alex가 뽑은 숫자들의 합보다 크다는 의미이다) 

이렇게 되면 굳이 두 사람의 점수를 모두 더한 다음에 비교하는 수고를 할 필요가 없다.

piles가 다 비워질 때까지 Alex는 총 점수가 가장 크도록 맨 앞과 맨 뒤 중 선택한 숫자를 더해가면 되고, Lee는 총 점수가 가장 작도록 맨 앞과 맨 뒤 중 선택한 숫자를 빼가면 된다. 

아래 코드는 LeetCdoe에 solution에서 예시 코드이다.

파이썬 코드

from functools import lru_cache
 
class Solution:
    def stoneGame(self, piles):
        N = len(piles)
 
        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player (홀수)
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))
 
        return dp(0, N - 1) > 0
 
game = Solution()
print(game.stoneGame([5,3,4,5]))

---

수학적으로 풀기

사실 이 분제는 좋아요 수보다 싫어요 수가 더 많다. Alex가 먼저 게임을 시작하게 될 경우에 수학적으로 계산하였을 때 항상 Alex가 이기기 때문일 것 같다.

복잡한 알고리즘을 짤 필요없이 항상 True를 반환해주면 시간 복잡도 O(1) 만에 문제를 풀 수 있다.

Alex가 먼저 뽑게 될 경우 맨 앞과 맨 뒤 중에, 좋은 수를 가져갈 수 있는 선택권이 항상 있다.

작은 예를 들어 보자. 두 개의 원소가 들어 있는 piles = [5, 7] 가 있다. Alex가 먼저 숫자를 뽑을 수 있다면 당연히 7을 뽑을 테고 게임에서 이기게 된다.

i	0	1
v	5	7

원소가 4개일 경우에도,

i	0	1	2	3
v	5	3	4	5

원소가 8개일 경우에도,

i	0	1	2	3	4	5
v	5	3	4	5	7	8

그러므로 원소가 N개라면 Alex가 먼저 숫자를 뽑는다고 하였을 때, Alex가 지려고 노력하지 않는 이상 항상 Alex가 이길 수 밖에 없다.