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

문제 링크

---

1. 아이디어

님 게임과 유사한데 돌을 가져갈 때 피보나치 수에 해당하는 수만큼만 가져갈 수 있다. 스프라그 그런디 정리를 활용해 각 돌 더미에 돌의 개수에 대한 그런디 수의 XOR 값으로 승패를 판단할 수 있다.

그런디 수를 구하기 위해 먼저 3×10⁶ 이하인 모든 피보나치 수를 구해줬다. 그런디 수의 경우 규칙이 크게 보이지 않고 300만 개정도면 전부 구해볼만도 해서 직접 구해줬다. mex를 위한 방문 체크 배열을 두고 현재 그런디 수에서 이동할 수 있는 모든 그런디 수에 대한 방문 체크를 해서 그런디 수를 구하는 과정을 반복했고, 이후 각 돌 더미에 대해 그런디 수의 XOR 값으로 승패를 판단해줬다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static final int MX = 3000000;

    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 + MX];
        boolean[] vis = new boolean[16];  // 전처리로 미리 크기 계산
        for (int i = 1; i <= MX; i++) {
            Arrays.fill(vis, false);

            for (int x : fibo) {
                if (i >= x) vis[g[i - x]] = true;
            }

            int mex = 0;
            while (vis[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");
        }
    }
}

2. 풀이 [C++]

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

const int MX = 3000000;
int fibo[32];  // 전처리로 미리 크기 계산
int g[1 + MX];
bool vis[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 <= MX; i++) {
        memset(vis, 0, sizeof(vis));

        for (int x : fibo) {
            if (i >= x) vis[g[i - x]] = true;
        }

        int mex = 0;
        while (vis[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";
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---