[C#] 백준 11868번 문제풀이

문제번호: 11868

문제명: 님 게임 2

문제링크: https://www.acmicpc.net/problem/11868

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 님 게임 문제를 풀었습니다. 님 게임은 배스킨라빈스 31 게임과 유사한 게임으로도 유명합니다.
이 문제에서의 님 게임은 일반적인 님 게임과는 조금 다르게 1개 이상의 돌 더미가 주어집니다. 플레이어들은 돌을 1개 이상씩 가져가고 마지막 더미에서 돌을 가져간 사람이 이기는 게임입니다.

위 게임은 누가 이길 수 있는지 예측할 수 있는 공식이 존재합니다. (아래링크 참고)
https://librewiki.net/wiki/%ED%95%84%EC%8A%B9_%EC%A0%84%EB%9E%B5_%EA%B2%8C%EC%9E%84

필승 전략 게임

 

풀이는 다음과 같습니다.

각 돌더미의 돌 개수를 입력받고 answer변수에 돌 개수를 XOR연산해 줍니다.
그렇게 모든 돌 개수가 연산되면 answer이 0일 경우 cubelover가 이기고 아닐 경우 koosaga가 이기게 됩니다.

그럼 원리를 간단하게 알아봅시다.

3, 4, 5가 있다고 할 때 2진수로 각각 변환하면 011, 100, 101이 됩니다. 여기서 1의 개수만 세어준다면 각각 2, 1, 2가 됩니다.
개수가 짝수, 홀수 짝수로 나왔네요. 여기서 알 수 있는 사실은 XOR은 홀짝 검사라는 것입니다.

XOR이 0일 때 cubelover가 이기는 이유는 모든 비트가 짝수상태이기 때문입니다. 모든 비트가 짝수라는 것은 반드시 어떤 더미에서 돌을 제거하면 비트는 홀수가 됩니다. 그럼 상대는 다시 비트를 맞춰서 짝수 상태로 되돌릴 수 있습니다. 그래서 XOR이 0이되는 상태는 항상 질 수밖에 없는 상태가 됩니다.

다음은 정답코드입니다.

static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    int[] piles = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

    int answer = 0;
    foreach(int pile in piles)
    {
        answer ^= pile; // xor연산
    }    

    if (answer == 0)
    {
        sw.WriteLine("cubelover");
    }
    else
    {
        sw.WriteLine("koosaga");
    }
}