C++로 푸는 '내가 이길 수 있을까?' 게임 – 비트마스크 DP 승패 판별하기

'100 만들기'라는 게임을 상상해 봅시다. 두 플레이어가 번갈아 가며 누적 합계에 1부터 10 사이의 정수를 하나씩 더하고, 누적 합계를 처음으로 100 이상 만든 플레이어가 승리합니다. 그렇다면 규칙을 바꿔 이미 사용한 숫자는 다시 쓸 수 없다면 어떻게 될까요?

예를 들어 두 플레이어가 1부터 15까지의 숫자가 담긴 공용 풀에서 중복 없이 번갈아 숫자를 꺼내, 누적 합계가 100 이상이 될 때까지 게임을 진행한다고 가정해 봅시다.

정수 maxChoosableInteger(선택 가능한 최대 숫자)와 정수 desiredTotal(목표 합계)이 주어질 때, 양쪽 플레이어 모두 최적의 전략으로 플레이한다고 가정하고 선공 플레이어가 확실하게 승리할 수 있는지 판별하는 것이 이 글의 목표입니다.

문제 조건상 maxChoosableInteger는 20 이하, desiredTotal은 300 이하라고 가정할 수 있습니다. 예를 들어 maxChoosableInteger = 20, desiredTotal = 11이 주어지면 결과는 false입니다. 선공이 어떤 숫자를 고르든 후공이 더 큰 숫자를 골라 한 번에 목표를 넘겨버릴 수 있기 때문에, 선공은 어떤 경우에도 이길 수 없습니다.

풀이 접근 방법

핵심 아이디어는 비트마스크(bitmask) 기반 메모이제이션입니다. 1부터 n까지 각 숫자의 사용 여부를 비트 하나로 표현하면, 최대 20개 숫자의 상태를 하나의 정수(mask)로 압축해 관리할 수 있습니다. 덕분에 가능한 모든 게임 진행 상황을 빠짐없이 탐색하면서도 중복 계산을 피할 수 있습니다.

구체적인 풀이 단계는 다음과 같습니다.

크기가 2^21인 배열 dp를 생성합니다.
n(선택 가능한 최대 숫자), s(남은 목표 합계), mask(사용된 숫자 집합)를 인자로 받는 solve() 함수를 정의합니다.
s <= 0이면 false를 반환합니다. 직전 차례의 플레이어가 이미 목표를 달성했으므로, 지금 차례인 플레이어는 패배한 상태입니다.
dp[mask]가 -1이 아니면 이미 계산된 값이므로 그대로 반환합니다.
ret := false로 초기화합니다.
i를 1부터 n까지 반복하며 다음을 수행합니다.
- mask의 i번째 비트가 0이라면(숫자 i가 아직 사용되지 않았다면) ret := ret OR (solve(n, s − i, mask XOR 2^i)의 부정)을 계산합니다.
dp[mask] := ret을 저장한 뒤 ret을 반환합니다.

메인 함수에서는 다음 순서로 처리합니다.

desiredTotal <= 0이면 true를 반환합니다. (첫 수를 두기 전에 이미 목표가 달성된 상태)
dp 배열 전체(0부터 2^21까지)를 -1로 초기화합니다.
desiredTotal이 1부터 n까지의 합(n × (n + 1) / 2)보다 크면 false를 반환합니다. 모든 숫자를 다 더해도 목표에 도달할 수 없기 때문입니다.
solve(n, desiredTotal, 0)을 호출해 결과를 반환합니다.

C++ 구현 예제

아래 코드를 통해 좀 더 구체적으로 이해해 봅시다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int dp[1 << 21];
    bool solve(int n, int s, int mask){
        if(s <= 0) return false;
        if(dp[mask] != -1) return dp[mask];
        bool ret = false;
        for(int i = 1; i <= n; i++){
            if(!((mask >> i) & 1)){
                ret |= (!solve(n, s - i, (mask ^ (1 << i))));
            }
        }
        return dp[mask] = ret;
    }
    bool canIWin(int n, int desiredTotal) {
        if(desiredTotal <= 0) return true;
        for(int i = 0; i < (1 << 21); i++)dp[i] = -1;
        if(desiredTotal > (n * (n + 1)/ 2))return false;
        return solve(n, desiredTotal, 0);
    }
};
main() {
Solution ob;
cout << (ob.canIWin(10,11));
}

입력

10
11

출력

출력이 0(false)이라는 것은, 위 입력 조건에서는 선공 플레이어가 어떤 전략을 사용하더라도 승리를 강제할 수 없음을 의미합니다.

이 풀이의 시간 복잡도는 O(2^n × n), 공간 복잡도는 O(2^n)입니다. n이 최대 20으로 제한되므로 2^21 크기의 배열만으로도 충분히 처리할 수 있습니다.