[동적계획법] NIM게임, 돌게임, 배스킨라빈스 31 게임 류의 풀이

이전 숫자에서 k개의 연속된 숫자를 외칠 수 있고 n을 외치면 승리하는 조건에서,

n+1 길이의 dp를 생성하고, 필승패를 1로 표기, 나머지는 0으로 표기한다.

 

[cpp]

// 최선의 수를 둘 때 선공이 승리할 수 있으면 True
#include <vector>
using namespace std;

bool NIM(int n, int k) {
    vector<int> dp(n + 1, 0);
    
    for (int i = n; i > 0; i--) {
        for (int j = i + 1; j <= min(i + k, n); j++) {
            if (dp[j] == 1) {
                dp[i] = 0;
                break;
            }
        }
        if (dp[i] != 0) {
            dp[i] = 1;
        }
    }

    for (int i = 1; i <= min(n, k); i++) {
        if (dp[i] == 1) {
            return true;
        }
    }
    
    return false;
}

 

[python]

# 최선의 수를 둘 때 선공이 승리할 수 있으면 True
def NIM(n, k):
    dp = [0] * (n + 1)
    for i in range(n, 0, -1):
        for j in range(i + 1, min(i + k, n) + 1):
            if dp[j] == 1:
                dp[i] = 0
                break
        else: dp[i] = 1
    for i in range(1, min(n, k) + 1):
        if dp[i] == 1:
            return True
    else: return False