292. Nim Game

Description

You are playing the following Nim Game with your friend:

• Initially, there is a heap of stones on the table.
• You and your friend will alternate taking turns, and you go first.
• On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
• The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

Example 1:

• Input: n = 4
• Output: false
• Explanation: These are the possible outcomes:
  1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
  2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
  3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
  In all outcomes, your friend wins.

Example 2:

• Input: n = 1
• Output: true

Example 3:

• Input: n = 2
• Output: true

Constraints:

• 1 <= n <= 2³¹ - 1

💡 Hint 1:
If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Submitted Code

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

Runtime: 0 ms | Beats 100.00%
Memory: *12.43** MB | Beats 49.30%

내가 돌을 가져간 뒤 남은 돌의 개수가 1, 2 또는 3일 경우 무조건 지게 되고, 반대로 4개이면 상대방이 몇 개를 가져가든 그 다음 턴에 내가 남은 돌을 끝낼 수 있다. 때문에 필승법은 항상 내 턴이 끝난 후 남은 돌이 4의 배수가 되도록 유도하는 것이다. 더 간단히 하면 시작 시 돌의 개수가 4의 배수일 때는 상대방도 최적의 전략을 사용하기 때문에 질 수밖에 없다.

n = 10

stone    me        friend
10       2(n%4)
8                  3
5        1(4-3)        
4                  2
2        2

return True

Other Solutions

1st

from functools import lru_cache

@lru_cache(None)
def canWinNim(n):
    if n <= 3:
        return True
    return not (canWinNim(n - 1) and canWinNim(n - 2) and canWinNim(n - 3))

리트코드에서 실제로 테스트하면 functools 모듈에서 lru_cache를 가져올 수 없어서 통과할 수 없었지만, 재귀 호출을 이용한 방법이어서 참고해봤다.