[BOJ] 백준 16889. 중복 없는 님 게임 (Platinum I)

알고리즘 중급 스터디에서 스프라그-그런디 정리를 공부한 후에 푼 문제이다.

정말 어렵다고 생각되는 문제.

문제는 아래와 같다.

https://www.acmicpc.net/problem/16889

16889번: 중복 없는 님 게임

---

의식의 흐름 및 해설

선공, 후공이 나누어져 있다. 그리고 두 플레이어는 항상 최선을 다하며, 돌이 몇 개 남아있는지 모두에게 공개되어 있다.

따라서 impartial game에 속하고, 돌 더미가 여러 개이므로 스프라그-그런디 정리를 이용할 수 있다.

 

이제 grundy number를 어떻게 구할 지가 문제다.

그동안의 문제들은 어떤 식으로 가져가든간에 특정 수에 대한 그런디 수가 일치했었는데,

이번 문제는 중복 없이 가져가야했기 때문에 어떻게 가져가냐에 따라 그런디 수가 매번 변했다.

 

예를 들어, g(0)=0, g(1)은 next state가 0뿐이므로 1이다.

그런데 g(2)에서 다음 상태로 0개, 1개가 가능하여 g(1)을 구하려 하면 g(1)은 이전에 1개의 돌을 이미 가져갔기 때문에 더 이상 돌을 가져갈 수 없는 상태이므로 0이다. 즉, 돌이 1개 있을 때 g(1)과, 돌이 2개 있을 때 g(1)의 값이 서로 다른 것이다! 문제 난이도가 굉장히 어려운 이유 중 하나이다.

 

g(2)는 위 작업으로 인해 1임을 알 수 있다.

g(3)은 mex({g(2),g(1),g(0)}) = mex({1,1,0}) = 2임을 알 수 있다.

이렇게 해서 g(6)까지 구해보자.

볼펜으로 적은 부분은 그런디수이다.

mex함수의 정의가 '집합에 포함되지 않은 정수 중 가장 작은 정수'를 반환하는 것임을 유의하자.

돌 더미의 개수가 ai개일 때, 항상 자기 자신의 개수만큼은 가져갈 수 있으므로 next state 집합에 0은 항상 포함된다.

그리고 그 외의 경우는 mex함수의 정의를 이용하기 위해 dfs를 돌려 그런디 수를 구해주자.

왜 dfs냐면, 자기 자신의 그런디 수를 구하기 위해 가능한 경우를 백트래킹 돌려서 각 경우들의 그런디 수를 구해준 후에, mex함수 리턴값을 구해야되기 때문이다. 즉, 재귀적 성질을 이용해야 한다.

 

dfs 코드는 아래와 같다.

int dfs(int k){
    if(!k)return 0;
    bool flag[MAX]={false};
    for(int i=1; i <= k; i++) {
        if (!vis[i]) {
            vis[i] = true;
            flag[dfs(k-i)]=true;
            vis[i] = false;
        }
    }
    for(int i=0;;i++){
        if(!flag[i])return i;
    }
}

특정 값에 대한 그런디 수를 반환해주는 코드를 작성했다.

60까지 계속 돌리면 당연히 시간초과이니까 한번 규칙을 구해보자.

1이 2개, 2가 3개, 3이 4개, ...

그렇다!

mex함수의 정의 때문인지 결국 트리 높이 (log2(ai))꼴의 규칙이 보인다!

 

ai: 1일 때 그런디 수 1 시작,

ai: 3일 때 그런디 수 2 시작,

ai: 6일 때 그런디 수 3 시작,

ai: 10일 때 그런디 수 4 시작,

ai: 15일 때 그런디 수 5 시작,

...

 

규칙이 (n(n+1)/2)꼴임을 알 수 있다~~

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 63;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
ll N,n,ans,d[MAX]={0,1,1,};
void solve(){
    int cnt=3;
    for(int i=3,j=2,k=0;i<MAX;i++,k++){
        if(k==cnt){
            k=0;
            cnt++;
            ++j;
        }
        d[i]=j;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>n;
        ans^=d[n];
    }
    cout<<(ans?"koosaga":"cubelover");
}

---

개인적으로 정말 어려웠지만, 그런디 수와 mex함수의 감을 잡는 데에 한 몫 해준 문제.