문제
koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.
일반적인 님 게임과는 다르게 님 게임 홀짝은 돌을 제거할 때 규칙이 있다. 짝수 개수만큼 돌을 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거할 수 없다. 예를 들어, 한 돌 더미에 있는 돌의 개수가 8개인 경우에는 2, 4, 6개만 제거할 수 있다. (8개는 제거할 수 없다) 돌을 홀수 개수 만큼 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거해야한다. 예를 들어, 돌의 개수가 8개인 경우에는 홀수 개수 만큼 돌을 제거할 수 없으며, 돌의 개수가 7개인 경우에는 2, 4, 6, 7개만 제거할 수 있다.
각 돌 더미에 돌이 0개 또는 2개 남은 경우에는 더 이상 돌을 제거할 수 없으며, 모든 돌 더미에 돌이 0개 또는 2개 남은 경우에 게임이 끝난다. 이때, 마지막 돌을 제거하는 사람이 게임을 이긴다.
게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.
입력
첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.
둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 2,147,000,000)가 주어진다. 모든 Pi가 2인 경우는 입력으로 주어지지 않는다.
출력
koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.
https://www.acmicpc.net/problem/11871
풀이
하나의 게임만을 고려해보자.
그런디수 G를
(오타 : 집합중이아닌 집합에 속하지않은.)
이제 문제의 조건을 살펴보자.
- 돌을 짝수개 제거할때는 전체를 제거 할 수 없다.
ex) G6 = {G2, G4} - 돌을 홀수개 제거 하는경우는 전체를 제거 할때 뿐이다.
ex) G7 = {G0, ...}
이제는 그런디수를 구할때 자주 사용하는 방법을 소개하겠다.
위 그림은 다른 문제의 그런디수를 나타낸것을 보여준 예시이다.
여기서 * 기호가 그런디수를 나타내는 G를 나타낸것이다.
표기법은
위의 그림으로 이를 설명하자면, 맨 왼쪽 *1~ *7 이 *n에 해당하고
가운데 집합이 나열되는데 집합의 원소는 *n과같은 다른 그런디수들이고 맨끝으로 보라색으로 표기한 해당집합에 없는 최소 정수가 최종적인 값이다.
가장 중요한것은 그런디 집합을 생각할때, 아래 4가지를 유의해야한다.
- 문제의 조건에서 종료조건인 그런디수의 집합은 공집합( {} ) 이며 최종값은 *0 이다.
- 그런디수의 '집합'은 최대한 0부터 1씩 쌓아올라가며 치환을 한다.
이때 비거나 없는 그런디수값이 최종적인 값(보라색표기)이다.- 그런디수의 '집합'내에서 치환할때 최종적인 값(보라색표기)들로 치환해야한다. 다른 그런디수 내의 집합으로 치환하지말자.
- (중요)집합을 치환하면 다른 모든 원소도 한번씩 치환해야 한다.
예로들어 아래와 같은 그림일때*7 을 구할때, {*3, *4, *6} 이 3개 모두 치환해주어야지, 그중 몇개만 치환하면 논리에 오류가 생긴다. *3 -> *1 // *4 -> *2 // *6 -> *2 이 되어,
{*1, *2, *2} = {*1, *2} 이렇게 원소갯수가 줄어들어도 상관없다.
이것에 속하지않는 최소 정수. *0 이 7의그런디값이된다.
밑에서 설명하겠지만, 여기서 2의그런디수는 0이고
3의 그런디수는 2 이고
4의 그런디수는 1일때,
4의 그런디수 중간에 2그런디수값이 0그런디수로 바뀌는데, 이때 치환한값은
보라색 표기로한 값이다. 중간의 공집합이나, 다른 집합내의 그런디수로 치환하지 말자.
설명이 장황했는데, 이제 이번 문제에 대한 그런디수들을 살펴보자.
*0 과 *2는 문제의 조건으로 이때 게임이 끝나므로, 집합은 공집합, 최종값은 0이다.(*0으로 볼수있다.)
*1의 의미는 게임판에 돌이 1개 남았을때 다음상태로 될수있는 그런디수들의 집합 중에 최소 정수이므로,
돌이 한개남았을경우 무조건 제거되므로 다음 상태의 그런디값은 {*0} 밖에없다.
문제는 *0 다음의 최소정수는 *1밖에 없으므로 최종값이된다.
*3 일때는 돌을 2개 또는 3개를 제거 할수 있으므로 {*1, *0}이고, 이상태는 집합내의 그런디수가 올바르게 쌓아져있으므로 그다음값인 *2가 최종값.
*4 일때 돌을 2개 밖에 제거 못하여 {*2}이고, 위에서 구한 최종값에의해서 {*0}이 되므로, 최종값은 *1 ...
그림에서 색깔별로 네모박스의 값이 화살표를 따라간 곳에 들어가며 치환되었음을 표현하였다.
이 문제의 경우 그런디값이 점화식을 세울 수 있으므로 세워보면, Gn의 n이 홀수일때, 짝수일때로 나뉘어진다.
결국 0에 입력받은 모든 그런디값을 순차적으로 xor연산시킨 결과값이
0 이면 cubelover가 이기고 0보다 크면 koosaga가 이기도록 코딩을 하면 된다.
처음 그런디수를 이해할때 집합개념을 너무 헷갈려서 많이 헤맸는데,
최대한 자세히 설명해볼려고 하여 길게 작성하였다.
많은 이해가 되었으면 한다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
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 grundy = 0;
void init();
void func();
void init() {
scanf("%d", &n);
while (n--) {
ll p;
scanf("%llu", &p);
p % 2 == 0 ? grundy ^= p / 2 - 1 : grundy ^= p / 2 + 1;
}
}
void func() {
grundy != 0 ? printf("koosaga") : printf("cubelover");
}
int main(void) {
init();
func();
return 0;
}