Hackerrank - Introduction to Nim Game, Misère Nim, Nimble Game

---

[풀이 - Introduction to Nim Game] : <Easy / 83.20%>

string nimGame(vector<int> pile)
{
    int result = 0;
    for(int i = 0; i < pile.size(); ++i)
        result ^= pile[i];
        
    if(result == 0)
        return "Second";
    else
        return "First";
}

# Charles L. Bouton 교수의 게임이론에 따르면 현재 상태가 '균형 상태'이면 다음 차례의 플레이어(First)는 패배한다.

# 각 pile의 수를 2의 거듭제곱으로 나타냈을 때 나타나는 수들이 쌍(pair)을 이룰 때 '균형 상태'라고 한다.

# '균형 상태'의 각 pile을 XOR 연산하여 0이 되면 '균형 상태'로 판단할 수 있다.

---

[풀이 - Misère Nim] : <Easy / 76.62%>

string misereNim(vector<int> s)
{
    int result = 0;
    int one = 1;
    for(int i = 0; i < s.size(); ++i)
    {
        result ^= s[i];
        one *= s[i];
    }
    
    if(one == 1)
    {
        if((s.size() % 2) == 1)
            return "Second";
        else
            return "First";
    }
    //
    if(result == 0)
        return "Second";
    else
        return "First";
}

# 마지막으로 stone을 옮기는 player가 지는 NimGame을 'MisereNim'이라고 한다.

# 'MisereNim'의 승리조건은 기존 NimGame 승리조건에

   [모든 pile의 stone이 '1'일 때 pile의 갯 수의 홀수 여부]를 추가

 

---

[풀이 - Nimble Game] : <Easy / 68.60%>

string nimbleGame(vector<int> s)
{
    int sum = 0;
    for(int i = 1; i < s.size(); ++i)
    {
        if((s[i] % 2) == 1)
            sum ^= i;
    }
    //
    if(sum == 0)
        return "Second";
    else
        return "First";
}

# coin의 개수가 짝수인 square는 결과에 영향을 주지 않는다

# square의 index가 NimGame의 pile과 동일한 의미를 갖는다