수정된 님(Modified Nim) 게임은 배열을 활용한 대표적인 최적화 게임 중 하나로, 선공 플레이어와 양측의 최적 수 선택에 따라 최종 승자를 예측하는 문제입니다.
게임 로직
이 게임에는 여러 개의 숫자가 담긴 배열이 주어지며, 두 명의 플레이어(player1과 player2)가 번갈아 가며 게임을 진행합니다. 두 플레이어의 목표는 각자 제거해야 할 숫자를 배열에서 모두 없애는 것이며, 구체적인 규칙은 다음과 같습니다.
- player1(A) : 3으로 나누어 떨어지는 숫자를 제거합니다.
- player2(B) : 5로 나누어 떨어지는 숫자를 제거합니다.
여기서 주목할 점은 15처럼 3과 5의 공배수는 어느 쪽 플레이어든 제거할 수 있다는 것입니다. 양쪽 모두 최적의 방식으로 원소를 제거한다고 가정할 때 최종 승자를 판별하는 것이 이 문제의 핵심입니다.
예시
배열 : {1, 5, 75, 2, 65, 7, 25, 6}
승자 : playerB
A가 75 제거 → B가 5 제거 → A가 6 제거 → B가 65 제거 → A가 둘 수 없음, B 승리!
풀이 접근 방식
풀이 코드는 먼저 다음 세 가지 값을 계산합니다.
- A만 제거할 수 있는 원소의 개수 (3의 배수)
- B만 제거할 수 있는 원소의 개수 (5의 배수)
- 두 플레이어 모두 제거할 수 있는 원소의 개수 (3과 5의 공배수)
이 중 두 플레이어가 공동으로 제거할 수 있는 원소의 개수가 승부를 결정짓는 핵심 변수입니다. A가 선공이므로 공통 원소가 존재하는 경우 A가 이를 먼저 가져갈 수 있고, 덕분에 A는 자신의 고유 원소 수보다 한 개 많은 상황에서도 승리할 수 있습니다. 즉, movesA + 1 > movesB이면 A가 이깁니다. 반면 공통 원소가 없는 일반적인 경우에는 제거해야 할 원소가 더 많은 플레이어가 승리합니다.
님 게임 솔루션 프로그램
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 5, 75, 2, 65, 7, 25, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int movesA = 0, movesB = 0, movesBoth = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 3 == 0 && arr[i] % 5 == 0)
movesBoth++;
else if (arr[i] % 3 == 0)
movesA++;
else if (arr[i] % 5 == 0)
movesB++;
}
if (movesBoth == 0) {
// 공통 원소가 없으면 단순 비교
if (movesA > movesB)
cout << "Player 1 is the Winner";
else
cout << "Player 2 is the Winner";
} else {
// 공통 원소가 있으면 A가 선점 가능
if (movesA + 1 > movesB)
cout << "Player 1 is the Winner";
else
cout << "Player 2 is the Winner";
}
return 0;
}
실행 결과
Player 2 is the Winner
결과 분석
주어진 배열 {1, 5, 75, 2, 65, 7, 25, 6}에서 75는 3과 5의 공배수(movesBoth), 6은 3의 배수(movesA), 그리고 5·65·25는 5의 배수(movesB)에 해당합니다. 따라서 movesA = 1, movesB = 3, movesBoth = 1이 되고, movesA + 1 = 2가 movesB인 3보다 작기 때문에 최종 승자는 player2(B)가 됩니다.