C++로 코인 게임 승자 예측하기: 최적 플레이 기반 승부 분석

이 게임에는 두 명의 플레이어 X와 Y가 참여합니다. 두 사람이 모두 최적의 전략으로 게임을 진행하고, X가 먼저 시작한다고 가정할 때 누가 승리할지 예측하는 것이 우리의 과제입니다.

게임 규칙

코인 게임에서는 각각 N개와 M개의 코인이 담긴 두 개의 더미가 주어집니다. 한 플레이어가 먼저 두 더미 중 하나를 선택한 뒤, 선택한 더미를 반으로 나누는 작업을 반복합니다. 이 과정은 어느 한쪽 플레이어가 더 이상 더미를 나눌 수 없게 될 때까지 계속되며, 마지막에 나눌 수 없는 상황에 놓인 플레이어가 패배합니다.

예시를 통해 문제를 살펴보겠습니다.

입력: M = 2 , N = 2
출력: X

해설 - X가 게임을 시작하여 M 더미(두 더미가 동일하므로 아무거나 선택 가능)를 고르고, 이를 둘로 나눕니다. 그러면 각 더미에는 코인이 하나씩만 남아 Y는 더 이상 나눌 수 있는 동작이 없습니다. 따라서 X가 승리하게 됩니다.

문제 해결 접근 방식

이 문제를 해결하려면 플레이어 X가 승리할 조건을 파악해야 합니다. 핵심 규칙은 다음과 같습니다.

• 두 더미 중 하나라도 짝수 개의 코인을 가지고 있다면, X가 항상 승리합니다.
• 두 더미 모두 홀수 개의 코인을 가지고 있다면, Y가 승자가 됩니다.

짝수 개의 코인이 담긴 더미는 적어도 한 번은 나눌 수 있기 때문에, 먼저 시작하는 X에게 유리한 조건이 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int isXWinner(int M, int N) {
    if (M % 2 == 0 || N % 2 == 0)
        return 1;
    return 0;
}
int main() {
    int M = 1, N = 2;
    cout<<"게임 시작!\n";
    if(isXWinner(M,N))
        cout<<"플레이어 X가 승자입니다";
    else
        cout<<"플레이어 Y가 승자입니다";
    return 0;
}

실행 결과

게임 시작!
플레이어 X가 승자입니다

위 코드에서 isXWinner 함수는 두 더미 중 하나라도 짝수인지 확인합니다. 짝수인 더미가 존재하면 1을 반환하여 X의 승리를 알리고, 그렇지 않으면 0을 반환하여 Y의 승리를 의미합니다. 시간 복잡도는 O(1)로 매우 효율적이며, 입력 크기와 관계없이 즉시 결과를 계산할 수 있습니다.