https://leetcode.com/problems/stone-game-ii
Stone Game II - LeetCode
Can you solve this real interview question? Stone Game II - Alice and Bob continue their games with piles of stones. There are a 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
leetcode.com
memoization dp로 해결한 문제였습니다
📕 풀이방법
📔 입력 및 초기화
📑 memoization을 위한 dict mem, 현 index까지 누적합 sum, 더미의 길이 pile_len을 선언 후 적절히 초기화합니다
📔 풀이과정
alice가 x개를 가져간다면 bob은 다음에 1 <= x <= 2 * max(이전 x, 이전 M)만큼 가져갈 수 있습니다. 즉, 많이 가져갈 수록 상대방이 가져갈 수 있는 더미 길이가 늘어나게 됩니다. alice는 최적의 플레이를 위해 앞으로 x개를 가져갔을 때 bob은 최적의 플레이를 한다면 몇개를 가져갈 수 있을지 계산을 해야합니다. 이는 dp를 이용해 모든 경우의 수를 분석할 수 있도록 점화식을 세우는 것이 가장 간단해 보입니다.
📑 점화식 설정
dp(piv, M): piv위치부터 현 플레이어가 1~2M개의 pile을 선택할 때 최종적으로 얻게되는 최대 돌 수
📑 dp함수 구현
1. 이미 계산된 mem이라면 이후 재귀함수는 호출할 필요가 없으므로 바로 반환합니다.
2. 현 플레이어가 최적 플레이시 piv 위치에서 얻을 수 있는 최댓값 best를 선언 후 0으로 초기화합니다.
3. 현 플레이어 차례에서 piv위치로부터 앞으로 남은 돌의 총합 remaining_candidate를 구해줍니다. piv가 0일때는 sum[-1]을 저장하도록 해주며 나머지의 경우는 sum[-1] - sum[piv-1] 입니다.
4. 현 플레이어가 가져갈 수 있는 x의 범위만큼 순회합니다. 순회하며 각자 최선의 플레이를 했을 때 현 플레이어가 가져갈 수 있는 돌의 최댓값을 best에 저장합니다. piv위치에서 가져갈 수 있는 x의 범위는 1 <= x <= min(2*m, pile_len - piv) 입니다. 이 때 상대 플레이어의 최적 플레이시 가지게 될 돌 수이므로 dp(piv + x, max(m,x))가 됩니다. 현 플레이어는 remaining_candidate - 상대 플레이어의 최적 플레이시 가지게 될 돌 만큼을 가져가게 되며 이때의 최댓값은 best에 저장합니다
5. mem[(piv,m)]을 best값으로 갱신합니다
📑 시간 복잡도
O(N^3): x만큼 dp를 재귀적으로 호출하기 때문입니다
📑 공간 복잡도
O(N^2): memoization key가 piv, m 2차원이기 때문입니다.
📔 정답 출력 | 반환
dp(0,1)을 반환합니다.
📕 Code
📔 Python3
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
mem = {}
sum = [piles[0]]
pile_len = len(piles)
for i in range(1, pile_len):
sum.append(sum[i-1] + piles[i])
# dp(piv, M): piv위치부터 현 플레이어가 1~2M 개의 pile을 선택할 수 있을 때 최종적으로 얻는 최대 돌 개수
def dp(piv: int, m: int):
if (piv,m) in mem:
return mem[(piv,m)]
best = 0
remaining_candidate = 0
if piv == 0:
remaining_candidate = sum[-1]
else:
remaining_candidate = sum[-1] - sum[piv-1]
for x in range(1, min(2*m, pile_len - piv)+1):
current = dp(piv + x, max(m,x))
opposite = remaining_candidate - current
best = max(best, opposite)
mem[(piv,m)] = best
return mem[(piv,m)]
return dp(0,1)*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.