11월 27일 - 핌버[BOJ/16877]

문제 해결 코드

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

public class Main {

    static final int MAX_LEN = 3_000_001; // 최대 돌 개수
    static int[] fibo = new int[32];      // 피보나치 수
    static int[] dp = new int[MAX_LEN];  // Grundy 수 저장

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

        // 피보나치 수 계산
        generateFibonacci();

        // Grundy 수 계산
        calculateGrundyNumbers();

        // 입력 처리
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int result = 0;

        for (int i = 0; i < N; i++) {
            int pile = Integer.parseInt(st.nextToken());
            result ^= dp[pile]; // Nim-Sum 계산
        }

        // 결과 출력
        System.out.println(result != 0 ? "koosaga" : "cubelover");
    }

    // 피보나치 수 생성
    private static void generateFibonacci() {
        fibo[0] = 1;
        fibo[1] = 1;
        for (int i = 2; i < 32; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
            if (fibo[i] > MAX_LEN) break; // 범위를 초과하면 중단
        }
    }

    // Grundy 수 계산
    private static void calculateGrundyNumbers() {
        for (int i = 1; i < MAX_LEN; i++) {
            boolean[] mex = new boolean[32]; // mex 계산을 위한 방문 배열
            for (int j = 0; j < 32; j++) {
                if (fibo[j] > i) break; // 피보나치 수가 현재 값보다 크면 중단
                mex[dp[i - fibo[j]]] = true;
            }
            // mex 값 중 가장 작은 값 찾기
            for (int k = 0; k < 32; k++) {
                if (!mex[k]) {
                    dp[i] = k;
                    break;
                }
            }
        }
    }
}

코드 설명

1. 피보나치 수 생성

private static void generateFibonacci() {
    fibo[0] = 1;
    fibo[1] = 1;
    for (int i = 2; i < 32; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
        if (fibo[i] > MAX_LEN) break; // 범위를 초과하면 중단
    }
}

• 피보나치 수는 돌을 제거할 때 필요한 수로 사용된다.
• 최대 돌 개수 MAX_LEN보다 작은 피보나치 수만 저장한다.
• 배열 fibo에 피보나치 수를 저장하고, 이후 Grundy 수 계산에 활용한다.

2. Grundy 수 계산

private static void calculateGrundyNumbers() {
    for (int i = 1; i < MAX_LEN; i++) {
        boolean[] mex = new boolean[32]; // mex 계산을 위한 방문 배열
        for (int j = 0; j < 32; j++) {
            if (fibo[j] > i) break; // 피보나치 수가 현재 값보다 크면 중단
            mex[dp[i - fibo[j]]] = true;
        }
        // mex 값 중 가장 작은 값 찾기
        for (int k = 0; k < 32; k++) {
            if (!mex[k]) {
                dp[i] = k;
                break;
            }
        }
    }
}

• Grundy 수는 특정 돌 개수에서 가능한 다음 상태들의 Grundy 수를 통해 계산된다.
• Mex(Minimum Excludant)는 현재 상태에서 도달할 수 없는 가장 작은 Grundy 수를 의미한다.
• 피보나치 수를 이용하여 가능한 모든 경우의 Grundy 수를 계산한다.

3. Nim-Sum 계산

int result = 0;
for (int i = 0; i < N; i++) {
    int pile = Integer.parseInt(st.nextToken());
    result ^= dp[pile]; // Nim-Sum 계산
}

• 모든 돌 더미의 Grundy 수를 XOR 연산으로 합산한다.
• 결과가 0이 아니면 첫 번째 플레이어가 이기고, 0이면 두 번째 플레이어가 이긴다.

So...

Grundy 수와 Nim 게임의 성질을 이해하고 적용해야 풀 수 있었다. Grundy 수를 계산하는 과정에서 Mex와 피보나치 수를 활용해 상태 전이를 모델링했다. 초반에는 피보나치 수의 범위와 Grundy 수 계산의 효율성을 고민했지만, 효율적인 메모이제이션과 Mex 계산으로 문제를 해결할 수 있었다. Nim 게임을 다룰 때의 기초부터 고급 응용까지 다룰 수 있는 좋은 문제였다.