[백준 C++] 11868 님 게임 2

문제

koosaga와 cubelover가 님 게임을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.

게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 109)가 주어진다.

출력

koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.

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

풀이

스프라그-그런디 알고리즘을 사용하면 매우 쉽게 풀 수 있는 문제이다. (스프라그-그런디 알고리즘 = https://velog.io/@cldhfleks2/Sprague-Grundy-Theorem)
문제는 n개의 돌무더기에 각각 p1, p2, p3... pn개의 돌이 쌓아져있을때
두 플레이어가 번갈아가며 하나의 돌무더기만 선택하여 그중 원하는 만큼 1개이상 돌을 빼고,
최종적으로 모든 돌무더기의 맨 마지막 돌을 빼는 사람이 이기는 게임이다.

위에 설명한대로 n개의 게임판. 돌무더기가 있고
각각에서의 그런디수를 정의한다음 모두 xor 연산하면 현재 이루어지는 전체게임의 그런디수가 정의된다.

따라서 이 문제에서는 하나의 돌무더기에잇는 돌의 수가 그 돌무더기. 게임판의 그런디수가 되도록 하는것이 요점이다.
(플레이어가 하나의 돌무더기에서 돌을 제거하는것은 자기 마음대로 1개이상 이므로..)

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::queue; using std::pair; using std::string; using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
int n;
ll p;
ll grundy = 0;

void init();
void func();

void init() {
    scanf("%d", &n);
    while(n--){
        ll p;
        scanf("%llu", &p);
        grundy ^= p;
    }
}

void func() {
    grundy ? printf("koosaga") : printf("cubelover");
}

int main(void) {
    init();
    func();


    return 0;
}