Nim Game

📚 문제

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 <= 231 - 1

💡 풀이

var canWinNim = function(n) {
return n % 4 ? true : false
};

🧮 경우의 수

✅ 코드를 짜고 나니 간단하지만
처음에는 개념을 이해하는데 조금 시간이 걸렸다.
한 사람당 3개까지 가져갈 수 있기 때문에 최대 경우의 수는 6개이다.

<나: 본인>
<상: 상대방>
1 -> 나
2 -> 나 나
3 -> 나 나 나
4 -> 나 상 상 상 / 나 나 상 상 / 나 나 나 상
5 -> 나 상 상 상 나 / 나 상 상 나 나 / 나 상 나 나 나 
6 -> 나 상 상 상 나 나 / 나 나 상 상 상 나 / 

스톤이 4개일 경우에는 어떻게 해도 상대방이 이기는 경우이고 다른 경우는 내가 이길 수 있는 경우의 수가 존재한다.

👉🏻 그래서 스톤의 개수를

• 4로 나누어서 떨어지는 경우면 내가 무조건 지기 때문에 false 리턴,
• 떨어지지 않으면 내가 이기는 게임이기 때문에 true를 리턴한다.