1140. Stone Game II

1140. Stone Game II

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

문제

내용에 수식이 많아서 이해하기 좀 어려웠다. 문제를 설명하자면 다음과 같다.
첫 번째 턴
M=1이므로 Alice는 1 <= X <= 2(즉 1개 또는 2개 선택할 수 있다.)

두 번째 턴(Alice가 1개 선택했을 때)
M = max(1,1) 이므로 1, Bob은 1 <= X <= 2(즉 1개 또는 2개 선택할 수 있다.)

두 번째 턴(Alice가 2개 선택했을 때)
M = max(1,2) 이므로 2, Bob은 1 <= X <= 4(즉 1개 또는 4개 선택할 수 있다.)

마찬가지로 세 번째 턴(BoB이 4개를 선택했을 때)
M = max(2,4)이므로 4, Alice는 1 <= X <= 8(1개 또는 8개를 선택할 수 있다.)

MiniMax 알고리즘

쉽게 말해 자기 턴일 때에는 최대값을 가져오고 상대 턴일 때에는 최소값을 가져와(상대방 입장일 때에는 최대값임) 비교한다. 즉 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 만들자 라며 나온 것이 바로 MiniMax Algorithm, 미니맥스 알 고리즘이다.

Example 1
piles = [2,7,9,4,4], Ouput =10 그림

그림으로 그리면 쉽게 이해 할 수 있다. 상대방의 최고의 수는 나에게 최소의 영향을 끼치는 것으로 생각하면 쉽다.

풀이

결과