[BaekJoon] #16877 - 핌버 [Java][C++]

문제 링크

---

1. 아이디어

돌 더미에서 피보나치 수만큼만 돌을 제거할 수 있는 님 게임인 핌버에서 승자를 구하는 문제다. 더미는 서로 독립이므로 더미마다 그런디 수를 구해 XOR하는 스프라그 그런디 정리를 쓰며, XOR한 값이 0이 아니면 선공이 이긴다. 돌이 $i$개인 더미의 그런디 수 $g(i)$는 피보나치 수 $f$만큼 제거해 도달하는 $g(i - f)$들의 mex이다. 그런디 수에서 뚜렷한 규칙은 보이지 않지만 더미의 크기가 최대 $3 \times 10^6$이고 이 이하의 서로 다른 피보나치 수는 31개뿐이라 $g(1)$부터 $g(3 \times 10^6)$까지 전부 구해도 약 $10^8$번의 연산이므로, 입력과 상관없이 모든 그런디 수를 미리 구해 두었다. mex는 이동해서 닿을 수 있는 그런디 수를 방문 체크 배열에 표시한 뒤 처음 비어 있는 값을 찾아 구하며, 이 배열의 크기는 그런디 수의 최댓값을 미리 확인해 정했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + K)$	$O(K)$

($N$ = 입력값 n, $K$ = 값의 범위)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 3_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int[] fibo = new int[32];  // 전처리로 미리 크기 계산
        fibo[0] = fibo[1] = 1;
        for (int i = 2; i < 32; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }

        int[] g = new int[1 + MAX];
        boolean[] seen = new boolean[16];  // 전처리로 미리 크기 계산
        for (int i = 1; i <= MAX; i++) {
            Arrays.fill(seen, false);
            for (int x : fibo) {
                if (i >= x) seen[g[i - x]] = true;
            }

            int mex = 0;
            while (seen[mex]) {
                mex++;
            }
            g[i] = mex;
        }

        int nimsum = 0;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (n-- > 0) {
            int p = Integer.parseInt(st.nextToken());
            nimsum ^= g[p];
        }

        if (nimsum != 0) {
            System.out.println("koosaga");
        } else {
            System.out.println("cubelover");
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAX = 3'000'000;
int fibo[32];  // 전처리로 미리 크기 계산
int g[1 + MAX];
bool seen[16];  // 전처리로 미리 크기 계산

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fibo[0] = fibo[1] = 1;
    for (int i = 2; i < 32; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }

    for (int i = 1; i <= MAX; i++) {
        memset(seen, 0, sizeof(seen));
        for (int x : fibo) {
            if (i >= x) seen[g[i - x]] = true;
        }

        int mex = 0;
        while (seen[mex]) mex++;
        g[i] = mex;
    }

    int nimsum = 0;

    int n;
    cin >> n;

    while (n--) {
        int p;
        cin >> p;
        nimsum ^= g[p];
    }

    if (nimsum) {
        cout << "koosaga";
    } else {
        cout << "cubelover";
    }
}

---