문제 개요
님 게임(Nim Game)은 양의 정수 N으로 표현되는 돌 더미가 주어지고, 두 명의 플레이어 'playerA'와 'playerB'가 번갈아 진행하는 게임입니다. 이 문제에서 우리의 목표는 님 게임의 최종 승자를 예측하는 프로그램을 작성하는 것입니다.
게임 규칙
님 게임의 규칙은 다음과 같습니다.
- 돌이 쌓여 있는 더미(힙)가 하나 있으며, 두 플레이어 'playerA'와 'playerB'가 참여합니다.
- 각 플레이어는 자신의 차례에 돌 더미에서 정확히 한 개의 돌을 가져갈 수 있습니다.
- 'playerA'가 항상 먼저 시작합니다.
- 마지막으로 돌을 가져간 플레이어가 게임의 승자가 됩니다.
예제로 문제 이해하기
입력: N = 6
출력: playerB
설명:
전체 돌의 개수 = 6, 플레이어들이 돌을 가져가는 순서는 다음과 같습니다.
playerA → playerB → playerA → playerB → playerA → playerB
해결 접근 방법
이 문제를 해결하는 한 가지 방법은 N 값과 게임 승자 사이의 일반적인 패턴(공식)을 찾는 것입니다. 몇 가지 N 값에 따른 승자를 살펴보겠습니다.
- N = 1일 때, 승자 = playerA
- N = 2일 때, 승자 = playerB
- N = 3일 때, 승자 = playerA
위 결과에서 다음과 같은 규칙을 도출할 수 있습니다.
- N이 홀수인 경우: playerA가 승자입니다.
- N이 짝수인 경우: playerB가 승자입니다.
이 규칙은 직관적으로도 설명할 수 있습니다. playerA가 먼저 시작하기 때문에 돌의 개수가 홀수라면 마지막 돌은 playerA가 가져가게 되고, 짝수라면 playerB가 마지막 돌을 가져가 승리하게 됩니다.
C++ 구현 예제
다음은 위 해결 방법의 동작을 보여주는 프로그램입니다.
#include<iostream>
using namespace std;
bool findGameofNimWinner(int N){
if(N%2 == 0)
return 0;
else
return 1;
}
int main(){
int N = 26;
cout<<"The winner of the Game of Nim is ";
findGameofNimWinner(N) ? (cout << "Player A") : (cout << "Player B");
return 0;
}
실행 결과
The winner of the Game of Nim is Player B
복잡도 분석
이 솔루션은 단순히 N을 2로 나눈 나머지만 확인하면 되므로 시간 복잡도는 O(1)이며, 별도의 추가 공간도 필요하지 않습니다. 따라서 N이 아무리 커져도 즉시 승자를 판별할 수 있는 매우 효율적인 방법입니다.