LeetCode 292(Nim Game, Python)

1. 문제 링크 

• https://leetcode.com/problems/nim-game/description/

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• Nim Game 규칙
  • table에 돌무더기가 있다고 가정했을 때,
  • 나와 나의 친구가 번갈아가면서 차례가 오고, 나 먼저 시작한다.
  • 각 차례에서, 1~3개의 돌을 무더기에서 제외할 수 있고, 
  • 마지막 돌을 제거하는 사람이 승자이다.
• 돌의 개수 n이 주어졌을 때, 내가 게임에서 이길 수 있다면 True, 그렇지 않다면 False를 반환한다.
  • 여기서, 나와 나의 친구는 optimally하게 play한다고 가정한다.
• 예시1)
  • n=4이면 
    • 내가 1개를 제거하면, 상대방이 3개를 제거해서 이기고,
    • 내가 2개를 제거하면, 상대방이 2개를 제거하여 이기고,
    • 내가 3개를 제거하면, 상대방이 1개를 제거하여 게임에서 이기게 되므로,
    • 내가 이길 가능성이 없어서 False를 반환한다.
  • n=1이면
    • 내가 1개를 제거하면 게임에서 이기기 때문에 True를 반환한다. 

 

3. 처음 풀이

• 해당 문제는 n=1일 때, n=2일 때,.. 의 경우의 수를 나열하면서 규칙을 찾는 문제라 생각했다. 
  • n=1이면 내가 1개를 제거하면 게임에서 이기므로 True
  • n=2이면 내가 2개를 제거하면 게임에서 이기므로 True
  • n=3이면 내가 3개를 제거하면 게임에서 이기므로 True
  • n=4이면, 내가 1~3개를 제거했을 때, 상대방이 3~1개를 제거할 수 있으므로 False
  • n=5이면, 1+4로 내가 1개를 제거하여 n=4일 때 상대방의 차례가 오는 것이므로, 상대방이 질 수밖에 없고, 나는 게임에서 이기므로 True
  • n=6이면, 2+4로 내가 2개를 제거하면 n=4일 일 때 상대방 차례이므로, True
  • n=7이면, 3+4로 True
  • n=8이면, 내가 1~3개를 제거했을 때, 상대방이 3~1개를 제거하면서 4개가 남을 수 있게 만들 수 있으므로 False가 된다.
• 여기까지 나열했을 때 찾은 규칙은
  • n이 4의 배수가 되면, 내가 지게 되는 케이스가 된다는 것. 
• 이에, 아래처럼 n%4 !=0 을 반환하는 코드로 작성하였다. 

class Solution:
    def canWinNim(self, n: int) -> bool:
        return  n % 4 != 0

 

4. 다른 풀이

• 대부분이 위의 풀이에서 벗어나지 않았다 :)