877. Stone Game

877. Stone Game

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

문제

풀이

DFS로 나타내면 위에 이미지 같이 된다. 우리가 알아야 할 것은 Alice의 최대 점수를 알아야 한다. 만약 최대 점수가 총합 / 2보다 크게 되면 (비기는 조건 이상이라면) 이길 것이고 작게 된다면 무조건 진다는 의미가 될 것이다.
이미지 상으로는 Alice가 5,5를 골랐을 때에 최대가 될 것이고 절반(8.5)보다 크므로 True가 될 것이다.

Min, Max 알고리즘을 사용하였다. Alice 차례 일 때엔 max값을 , Bob 차례일 땐 min값(Bob이 선택할 수 있는 가장 좋은 경우 => Alice입장에선 가장 나쁜 선택임)을 구하여 서로 가장 좋은 선택을 하였을 때 합의 절반(비기는 경우)보다 클 경우 Alice가 이기는 것이고 지는 경우 Bob이 이기는 것이다.

결과