1690. Stone Game VII

1690. Stone Game VII

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

문제

풀이

DFS 트리 구조로 나타내면 다음과 같다.

문제에서 원하는 것은 Alice와 Bob 점수 차이를 알고 싶다. Alice는 Bob과 차이를 많이 내기를 원하고 Bob은 Alice와 차이를 적게 내고 싶어한다.
Bob에 경우 (3,1), (5,3)노드에서 합은 4, 8이다. DFS 리턴되는 값은 Alice와 Bob차이값을 리턴받는데 이 차이가 클수록 다음 Alice 차이를 최소화 할 수 있다. 즉 (4-3), (8-5)중 (8-5)가 더 크므로 (5,3)쪽으로 나타낼 수 있다.

풀이(DFS)

결과(DFS)