문제 소개
두 명의 플레이어가 함께 즐기는 '님 게임(Nim Game)'을 생각해 봅시다. 돌무더기가 하나 주어지고, 플레이어들은 번갈아 가며 자신의 차례에 1개부터 3개까지의 돌을 제거합니다. 마지막 돌을 가져가는 사람이 승자가 되며, Player1이 항상 먼저 시작합니다. 또한 두 플레이어 모두 매우 똑똑하여 항상 최적의 전략으로 게임을 진행한다고 가정합니다.
우리가 설계해야 할 것은 돌무더기에 있는 돌의 개수 n이 주어졌을 때, Player1이 이 게임에서 승리할 수 있는지를 판단하는 알고리즘입니다.
예시
입력이 5라고 가정해 보겠습니다. 이 경우 출력은 true입니다. 그 이유는 다음과 같습니다. 돌이 5개 있는 상태에서 Player1이 처음에 1개를 가져가면, Player2가 1~3개 중 몇 개를 가져가더라도 반드시 1개 이상의 돌이 남게 되어, Player1이 마지막 돌을 가져가며 승리할 수 있습니다.
해결 접근 방법
놀랍게도 이 문제는 아주 간단한 한 단계만으로 해결할 수 있습니다:
n을 4로 나눈 나머지가 0이 아니면 true를 반환하고, 나머지가 0이면 false를 반환한다.
왜 하필 4일까?
그 원리를 살펴보겠습니다. 만약 자신의 차례에 남은 돌이 정확히 4개라면, 어떤 선택(1개, 2개, 3개)을 하든 상대방이 남은 돌을 전부 가져갈 수 있는 상황이 됩니다. 즉, 4의 배수 상황은 필패(必敗)입니다.
따라서 시작할 때 돌의 개수 n이 4의 배수라면, 상대방이 어떻게 하든 자신이 계속 4의 배수 상황을 유지하게 만들 수 있으므로 선공은 반드시 집니다. 반대로 n이 4의 배수가 아니라면, 선공이 첫 차례에 적절한 개수를 가져가 상대방에게 4의 배수 상황을 넘겨줌으로써 승리를 보장할 수 있습니다.
구현 예제
아래의 C++ 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canWinNim(int n) {
return n%4!=0;
}
};
main(){
Solution ob;
cout << (ob.canWinNim(5));
}
입력
5
출력
1
마무리
이 문제는 시간 복잡도 O(1), 공간 복잡도 O(1)로 해결되는 대표적인 수학적 사고력 문제입니다. 겉보기에는 복잡한 게임 이론처럼 보이지만, '4의 배수'라는 핵심 패턴만 발견하면 단 한 줄의 코드로 답을 구할 수 있다는 점이 흥미롭습니다.